Berechnen Primzahlen und Anhängen an eine Liste

Question

Ich habe vor kurzem angefangen zu versuchen, Probleme auf Projekt Euler mit Python zu lösen, und haben diese Straße stoßen bei dem Versuch, Primzahlen zu berechnen und sie an eine Liste anfügen. Ich habe den folgenden Code geschrieben, aber ich bin verwirrt, warum es nichts ausgibt, wenn ich es ausführe.

import math 

primes = [] 

def isPrime(i): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for i in range(3,int(sqrt(number))+1): 
     if number%i==0: 
      return False 
    return True 

for i in range (1, 9999999): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 
print(primes) 

Answer 1

Versuchen:

import math 

primes = [] 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for i in range(3,int(math.sqrt(number))+1): 
     if number%i==0: 
      return False 
    return True 

for i in range (1, 9999999): 
    if isPrime(i) == True: 
     primes.append(i) 

print(primes) 

Answer 2

Try this:

import math 

primes = [] 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for ind in range(3,int(math.sqrt(number))+1): 
     if number%ind==0: 
      return False 
    return True 

for i in range (1, 100): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 

print(primes) 

es zu zeigen, arbeiten, drucke ich die ersten 100:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

Answer 3

eine bedingte Liste Verständnis verwenden:

primes = [ 
    i for i in range(1, 9999999) 
    if i == 2 
    or i > 2 # Anything less than 2 is not prime. 
    and i % 2 # No evens (except for 2 above) 
    and all(i % n for n in range(3, int(i ** 0.5) + 1))] 

>>> primes[:10] 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

>>> primes[-10:] 
[9999889, 
9999901, 
9999907, 
9999929, 
9999931, 
9999937, 
9999943, 
9999971, 
9999973, 
9999991] 

Answer 4

Der einfachste Weg, dies zu tun ist, etwas zu verwenden, das als Sieve genannt wird. So erhalten Sie alle Primzahlen bis zu einer Million.

def mark_sieve(sieve, x): 
    for i in range(x+x, len(sieve), x): 
     sieve[i] = False 

sieve = [True]*(10**7+1) 
for x in range(2, int(len(sieve)**0.5 + 1)): 
    if sieve[x]: mark_sieve(sieve, x) 

Die Idee ist, dass wir zunächst eine Liste sieve genannt erstellen und alle Werte auf True zuweisen, was bedeutet, dass wir jetzt alle Zahlen auf 1 Million (einschließlich) unter Berücksichtigung wie Primzahlen sind. Wir werden über jede Zahl auf eine Million iterieren und jedes Vielfache davon als False in der sieve-Liste markieren. Um zu optimieren, iterieren wir nur auf die Quadratwurzel von 1 Million. Warum? Weil eine Zahl nicht zwei Faktoren haben kann, die beide größer als die Quadratwurzel der Zahl sind. Wenn wir also eine Zahl durch ganze Zahlen bis zur Obergrenze ihrer Quadratwurzel und noch unteilbar teilen, bedeutet das, dass sie eine Primzahl ist.

Wenn Sie also überprüfen möchten, ob eine Zahl prim ist, können Sie einfach sieve[some_number] verwenden. Wenn es False zurückgibt, ist es kein Prime. eine Liste von Primzahlen erhalten Sie [x for x in range(len(sieve)) if sieve[x]]

EDIT Geschwindigkeit Vergleiche verwenden -

import timeit 
import math 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for ind in range(3,int(math.sqrt(number))+1): 
     if number%ind==0: 
      return False 
    return True 

def mark_sieve(sieve, x): 
    for i in range(x+x, len(sieve), x): 
     sieve[i] = False 


# Other approaches 
time_0 = timeit.default_timer() 
primes = [] 
for i in range (1, 10**6+1): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 

# Sieve Approach 
time_1 = timeit.default_timer() 
sieve = [True]*(10**6+1) 
sieve[0] = False #because we wont consider zero and one as primes 
sieve[1] = False 
for x in range(2, int(len(sieve)**0.5 + 1)): 
    if sieve[x]: mark_sieve(sieve, x) 

primes_2 = [x for x in range(len(sieve)) if sieve[x]] 

time_2 = timeit.default_timer() 
time_1-time_0 # 12.423080921173096 seconds 
time_2-time_1 # 0.9901950359344482 seconds 

Für eine 100 Tausend Zahlen, unter Verwendung von Sieben mehr als 12-mal schneller ist. Für eine Million wird dieses Verhältnis 90. Auch wenn ich so viele Zahlen verwende, würde ich davon abraten, Listen anzufügen. Initiieren Sie stattdessen eine Liste und weisen Sie dann Werte zu.

Answer 5

Wenn Sie eine Liste mit Primzahlen erstellen, kann es effizienter sein, diese Liste als Teil Ihrer Lösung zu verwenden.

Zum Beispiel diese Schleife:

for i in range(3, int(math.sqrt(number)) + 1): 

Für die prime 1009 testen ~ 30 Zahlen, aber es gibt nur 10 Primzahlen kleiner als die Quadratwurzel von 1009, die tatsächlich müssen getestet werden. Und dieser Unterschied wächst immer weiter.

Mit unserer wachsenden prime Liste als Teil der Lösung:

primes = [2] 

for number in range(3, 9999999 + 1, 2): # only test odd numbers 

    for prime in primes: 
     if prime * prime > number: # we're past sqrt, a prime! 
      primes.append(number) 
      break 

     if number % prime == 0: # a composite 
      break 

print(*primes[:10], '...', *primes[-10:]) 

nirgendwo so schnell wie @ ClockSlave des Siebes, wird aber wahrscheinlich vor vielen anderen Lösungen beenden.

Answer 6

Jetzt funktioniert es, ich die Zahlen auf 999

import math 

primes = [] 


def isPrime(number): 
    if number <= 1: 
     return False 
    for i in range(2, int(math.sqrt(number)) + 1): 
     if number % i == 0: 
      return False 
    return True 

for i in range(1, 999): 
    if isPrime(i): 
     primes.append(i) 

print(primes) 

[OUTPUT] shortned haben:

[2, 3, 5, 7, 11, 13, 17 , 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 34 7, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Answer 7

Ihr Algorithmus, um alle Primzahlen in [0,9999999] zu erhalten, ist nicht sehr effizient. Es braucht eine lange Zeit, um es zu tun, so dass Sie die Ausgabe nicht sehen können, wenn Sie es ausführen. Es ist nur, weil es nicht getan wurde. Für einen schnelleren Algorithmus könnten Sie this heraus überprüfen