Suche nach der 10001sten Primzahl (in Python)?

Question

Ich versuche derzeit, eine Implementierung des Siebes von erasthonese zu verwenden, aber es dauert immer noch eine sehr lange Zeit, um eine lange Liste von Primzahlen zu finden.

def sieve(n=1000000): 
    not_prime = [] 
    prime = [] 
    for i in range(2, n+1): 
     if i not in not_prime: 
      prime.append(i) 
      for j in range(i*i, n+1, i): 
       not_prime.append(j) 
    return prime[10002] 

habe ich versucht, hart zu codieren das Sieb, zu welchem ​​Wert laufen soll und hoffentlich ist es lange genug, so dass ich das 10002. Element finden. Die Laufzeit ist derzeit ein großes Problem, daher werden alle Tipps oder Ratschläge zur Senkung der Laufzeit oder sonst etwas geschätzt.

Answer 1

Wenn Sie daran interessiert sind, diesen Code zu verbessern, dann verwenden Sie als erstes eine set, um die Nicht-Primzahlen zu speichern.

Dies verhindert die Wiederholung von Nummern innerhalb der Liste und macht die Suche innerhalb der Liste schnell. Dies wird Ihre Laufzeit erheblich verbessern.

In [1]: %timeit -n 1 -r 1 sieve(10000) 
1 loops, best of 1: 775 ms per loop 

In [2]: %timeit -n 1 -r 1 sieve_set(10000) 
1 loops, best of 1: 5.85 ms per loop 

nun die 10.001 prime zu finden, ist erreichbar:

In [3]: %timeit sieve_set(105000) 
10 loops, best of 3: 26.6 ms per loop 

In [4]: sieve_set(105000)[10000] 
Out[4]: 104743