Trouver le n-ième nombre premier à l'aide de Python

Lorsque j'exécute ce code, même pour le compte de la 10e premier numéro (au lieu de 1000), je reçois un biaisée/cric de sortie--tous les "non prime" sur les titres pour mon is_composite variable, mon test_num me donne des premiers et des nombres composés, et mon prime_count est éteint

Certaines des réponses que les développeurs ont partagé utiliser les fonctions et les mathématiques à l'importation--c'est quelque chose que nous n'avons pas encore couverts. Je ne suis pas en essayant d'obtenir le plus efficace de répondre; je suis juste essayer d'écrire réalisable code python pour comprendre les bases de la boucle.

  # test a prime by diving number by previous sequence of number(s) (% == 0).  Do this by
  # counting up from 1 all the way to 1000.

test_num = 2 #these are the numbers that are being tested for primality
is_composite = 'not prime' # will be counted by prime_count
prime_count = 0 #count the number of primes


while (prime_count<10): #counts number primes and make sures that loop stops after the 1000th prime (here: I am just running it to the tenth for quick testing)


 test_num = test_num + 1   # starts with two, tested for primality and counted if so
 x = test_num - 1  #denominator for prime equation

 while (x>2):   
  if test_num%(x) == 0:
   is_composite = 'not prime'
  else: 
   prime_count = prime_count + 1 
  x = x - 1 


  print is_composite
  print test_num
  print prime_count
Ce précisément ne fonctionne pas?
Votre algorithme est lente, l'affiner à l'aide de la théorie des nombres. Plus précisément, uniquement de contre-vérifier les nombres premiers inférieur ou égal à la racine carrée du nombre actuel.
Hors sujet: quelques commentaires dans votre code sont corrects, d'autres sont évidents: while x > 2: # runs while x is greater than 2 est évident. En général: commentaire le pourquoi, pas le ce que.
Vous et moi avons des idées différentes pour "gros" nombres premiers. Pour moi, un grand nombre premier est assez grande pour que tous les nombres premiers de moins que le candidat de nombre premier occuperait plus de mémoire (espace sur le disque dur?) que ce qui est disponible sur la machine (groupe?) test le candidat premier de primalité. Pour moi, le premier environ 2^40 nombres premiers sont petits
le problème n'est pas la cause des devoirs à la maison, mais avec votre approche: si vous a venir avec cette question et a dit "j'ai fait ceci et cela, et j'ai ce problème ici" ce serait de montrer que vous étiez vraiment perplexe après avoir fait l'effort. À venir et de dire "j'ai mal" avec un code qui, au premier abord, n'ont même pas une instruction print, montre un manque d'effort.

OriginalL'auteur zkidd | 2010-10-07

  1. 3

    Voir les conseils donnés par MIT pour votre affectation. Je cite ci-dessous:

    1. Initialiser certaines variables d'état

    2. Générer tous (bizarre entiers > 1 comme candidats pour être le premier

    3. Pour chaque candidat, entier, le test si c'est le premier

      3.1. Un moyen facile de le faire est de tester si les autres integer > 1 uniformément divise le candidat avec 0 reste. Pour ce faire, vous pouvez utiliser l'arithmétique modulaire, par exemple, l'expression a%b renvoie le reste de la division de l'entier a par l'entier b.

      3.2. Vous pourriez penser entiers, vous devez vérifier que les diviseurs – certainement, vous n'avez pas besoin d'aller au-delà de la candidat vous de vérifier, mais comment beaucoup plus tôt, pouvez-vous arrêter la vérification de?

    4. Si le candidat est premier, imprimer quelques informations pour savoir où vous en êtes dans le calcul, et de mettre à jour les variables d'état

    5. Arrêtez-vous lorsque vous atteignez un niveau approprié de la condition de fin. Dans la formulation de cette condition, n'oubliez pas que votre programme ne génère pas de le premier (2).

    Il pourrait ressembler à ceci:

    def primes(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]
    hier je suis allé à travers ces conseils, mais je suis toujours avoir des problèmes. d'où mon post.
    Sentiment assez mauvais que je me suis poser cette question même si je suis allé à travers ces conseils et re-regardé la conférence.
    Vous voudrez peut-être avoir un coup d'oeil à solutions plus efficaces pour obtenir l'Pythonic.

    OriginalL'auteur Wok

  2. 1

    Tout d'abord, à partir de la vague description de votre premier algorithme de vérification, il semble que vous vérifier le numéro de tous, jusqu'à le nombre que vous êtes les tests de primalité. Cependant, dans la réalité, vous n'avez qu'à tester jusqu'à la racine carrée de ce nombre. Une poursuite de l'optimisation serait de supprimer tous les numéros en dehors de deux (vous pouvez le faire par incrémentation par deux à partir de l'un et de test 2 séparément), vous vous retrouvez avec:

    def isprime(test):
    if test == 2: return True
    if test < 2 or test % 2 == 0: return False
    return not any(test % i == 0 for i in range(3, int(sqrt(test)) + 1, 2))

    Puis tout ce que vous avez à faire est de parcourir les nombres de 2 en haut de vérifier s'ils sont le premier et ajouter un à votre compteur si elles le sont. Lorsque vous atteignez 1000 arrêter et de sortie, le numéro est transmis à la fonction isprime.

    Bien sûr, il existe d'autres méthodes plus efficaces et, personnellement, je préfère le Crible d'Atkin. Mais ce serait à vous de les mettre en œuvre, mon algorithme permettra de servir vos fins.

    Edit: j'ai remarqué que votre commentaire que "rien n'est de retour/passe", qui serait dû à l'inefficacité de votre algorithme, si vous attendez suffisamment longtemps, vous obtiendrez une réponse. Cependant, je remarque que vous n'avez pas l'impression de déclaration dans le code que vous avez fournies, je suis en espérant que le code qui votre course en a un.

    from math import sqrt

def isprime(test):
    if test == 2: return True
    if test < 2 or test % 2 == 0: return False
    return not any(test % i == 0 for i in range(3, int(sqrt(test)) + 1, 2))

test_num = 2
prime_count = 1

while (prime_count< 1000): 

 test_num = test_num + 1  

 if (isprime(test_num)):
     prime_count += 1

print test_num
    Vous n'avez pas besoin d'écrire un distinct isprime fonction. Vous pouvez vérifier l'ex-premier entiers trouvé que les diviseurs de l'actuel, puisque vous faites une suite croissante.
    Jetez un oeil à rwh_primes(n) par exemple.
    Le mien est tout simplement un algorithme de remplacement, il permet d'obtenir le même résultat de manière moins efficace. J'ai fourni l'alternative Crible d'Atkin si zkidd voulu le regarder.
    Thnx wok et njak32--je vais tout regarder. Mais maintenant, je suis en cours d'exécution du programme, il semble comme il va "49" et l'arrêt. J'ai ajouté dans l'instruction print, je suis en utilisant. Mais le premier comte de n'aller jusqu'à 1000. Pouvez vous vérifier pour voir si le ci-dessus est la bonne?
    Commencer prime_count à 1, comme vous n'êtes pas de comptage de 2 en votre méthode actuelle.

    OriginalL'auteur ajnatural

  3. 0

    C'est un code que j'ai écrit en C++. Mais la mentalité doit être le même.

    // This code was written by Mert Ener
#include <time.h>
#include <vector>
#include <iostream>

private: System::Void button1_Click_1(System::Object^  sender, 
                                          System::EventArgs^  e) { 
    using namespace std;
    UInt64 cloc = clock();
    long m = 1;
    long k = long::Parse(textBox1->Text)-2;   // The text you entered 
    std::vector<long> p(1,2);                 //   for the nth prime
    for( long n = 0; n <= k; n++ ) {
        m += 2;
        for( long l = 1; l <= n; l++ ) {
            if (m % p[l] == 0) {
                m += 2;
                l=0;}}
        p.push_back(m);}
    textBox2->Text = p[k+1].ToString(); // The textbox for the result.
    MessageBox::Show("It took me " + (clock() - cloc).ToString() 
                     + " milliseconds to find your prime.");}

    OriginalL'auteur Flashbond

  4. -1

    Ce code ci-dessous génère une liste des nombres premiers jusqu'à 1 million de dollars.
    L'utilisation de cette liste, vous pouvez tester les nombres premiers < 1 Billion de dollars dans un assez rapide.
    Cela va un peu plus vite que le temps pour 10 à 12 chiffres les nombres premiers.

    import math
from itertools import islice
# number of primes below the square root of x
# works well when x is large (x > 20 and much larger)
numchecks = lambda x: int((math.sqrt(x))/(math.log(math.sqrt(x)) - 1.084)) + 1

primes = [2,3,5]
primes = primes + [x for x in range(7, 48, 2) if all((x%y for y in islice( primes, 1, int(math.sqrt(x)) )))]
primes = primes + [x for x in range(49, 2400, 2) if all((x%y for y in islice( primes, 1, numchecks(x) )))]
primes = primes + [x for x in range(2401, 1000000, 2) if all((x%y for y in islice( primes, 1, numchecks(x) )))]

    Vous pouvez augmenter le nombre de sauvé les nombres premiers en étendant le processus ci-dessus, mais le programme va prendre du temps (mais une seule fois).

    Dans votre code, vous pouvez tester si 'test_num" est le premier à l'aide de la suite...

    test_num = 23527631
if test_num<100:
    checks = int(math.sqrt(test_num))
else:
    checks = numchecks(test_num)

isPrime = all(test_num%x for x in islice(primes, 0, checks))
print 'The number is', 'prime' if isPrime else 'not prime'
print 'Tested in', checks, 'divisions'
    pourquoi ne pas isPrime = all(test_num % x for x in it.islice(primes, 0, checks)). islice peut-être exagéré, mais all est la seule façon d'aller ici 😉
    façon à le rendre encore plus rapide!! Merci.

    OriginalL'auteur Rajan