Recherche du nième nombre premier en utilisant Python

Question

Lorsque j'exécute ce code, même si je compte juste pour le 10e nombre premier (au lieu de 1000), je reçois une sortie asymétrique - tous les titres "non premiers" pour ma variable is_composite, mon test_num me donne des nombres premiers et composites, et mon prime_count est éteint

Certaines des réponses que les développeurs ont partagé utilisent des fonctions et l'importation de maths - c'est quelque chose que nous n'avons pas encore couvert. Je n'essaie pas d'obtenir la réponse la plus efficace; J'essaye juste d'écrire du code Python réalisable 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 

Answer 1

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

1. Initialiser des variables d'état

2. Generate tous (impairs) entiers> 1 comme des candidats au premier

3. Pour chaque entier candidat, le test que ce soit prime

   3.1. Une façon simple de faire ceci est de tester si un autre entier> 1 divise uniformément le candidat avec 0 reste. Pour ce faire, vous pouvez utiliser arithmétique modulaire, par exemple, l'expression a% b renvoie le reste après la division de l'entier a par l'entier b.

   3.2. Vous pourriez penser à quels entiers vous devez vérifier en tant que diviseurs - certainement vous n'avez pas besoin d'aller au-delà du candidat que vous vérifiez, mais combien de temps pouvez-vous arrêter de vérifier?

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

5. Arrêtez-vous une condition de fin appropriée.En formulant cette condition, n'oubliez pas que votre programme n'a pas généré le premier prime (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]] 

Answer 2

tout d'abord, de la vague description de votre premier algorithme de vérification, il semble que vous vérifiez chaque numéro au nombre que vous testez primalité. Cependant, en réalité, vous devez seulement tester jusqu'à la racine carrée de ce nombre. Une autre optimisation serait de supprimer tous les nombres pairs en dehors de deux (vous pouvez le faire en incrémentant par deux d'un et d'essai 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)) 

Alors tout ce que vous avez à faire est itérer à travers les numéros de 2 vers le haut en vérifiant s'ils sont premiers et en ajoutant un à votre compteur s'ils le sont. Lorsque vous atteignez 1000, arrêtez et affichez le nombre transmis à la fonction isprime.

Bien sûr, il existe d'autres méthodes plus efficaces, je préfère personnellement le Sieve of Atkin. Mais ce serait à vous de l'implémenter, mon algorithme servira vos objectifs.

Editer: J'ai remarqué que vous dites que 'rien ne se passe', ce qui serait dû à l'inefficacité de votre algorithme, si vous attendez assez longtemps, vous obtiendrez une réponse. Cependant, je remarque que vous n'avez aucune instruction d'impression dans le code que vous avez fourni, j'espère que le code dont vous disposez 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 

Answer 3

Ce code génère ci-dessous une liste de nombres premiers jusqu'à 1 million. En utilisant cette liste, vous pouvez tester les nombres premiers < 1 trillion d'une manière raisonnablement rapide. Cela fonctionne assez rapidement pour les nombres premiers de 10-12 chiffres.

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 nombres premiers enregistrés en élargissant le processus ci-dessus, mais le programme prendra beaucoup de temps (mais une seule fois processus).

Dans votre code, vous pouvez tester si 'test_num' est premier en utilisant les éléments suivants ...

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' 

Answer 4

Ce code j'ai écrit pour C++. Mais la mentalité doit être la 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.");}