Ich versuche, ein Eratosthenes-Sieb in Python zu schreiben. Ist das richtig und wie kann ich es schneller machen?

Question

Mögliches Duplikat:
Schnellster Weg zur Auflistung aller Primzahlen unter N in Python

Ich programmiere noch nicht sehr lange, und ich mache das nur zum Spaß, und ich weiß nicht viel über fortgeschrittenes Python, aber... Ich habe das hier geschrieben und wollte wissen, ob es tatsächlich ein Eratosthenes-Sieb-Programm ist, und wenn ja, wie ich es schneller machen könnte. Ich möchte nicht wirklich, dass jemand ein Programm postet, das eine Lösung ist, sondern mir eher sagen, wie ich meins anpassen könnte.

def eratSieve(n):
    all = []
    for a in range(2, n+1):
        all.append(a)               
    for b in all:                       
        for i in range(2,int(round(len(all)/b))):
            while i*b in all:
                all.remove(i*b)
                i+=1
    return all

Vielen Dank für Ihre Hilfe.

BTW - Es ist in Python 2.7

Answer 1

Ich stimme mit Gianluca überein und habe eine mögliche Lösung: Behalten Sie Ihr Hauptarray ( all ) als bools und markieren Nicht-Primzahlen, entfernen sie aber nicht. Es könnte auch schneller sein, weil Sie die Listengröße nicht ändern.

Eine Kleinigkeit: Sie können einfach schreiben all = range(2, n+1) am Anfang, wenn Sie sie als Ints behalten wollen.

Answer 2

Ihre Methode führt zu falschen Ergebnissen. Der Fehler liegt in der for i Schleife. Hier ist es, angepasst, und mit einem Test:

known_primes = [
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,347,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,1009,1013,
1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,
1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,
1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,
1453,1459,1471,1481,1483,1487,1489,1493,1499]
def eratSieve(n):
    all = []
    for a in range(2, n+1):
        all.append(a)               
    for b in all:                       
        for i in all[all.index(b):]:
            while i*b in all:
                all.remove(i*b)
                i+=1
    return all

for N in range(1500):
    for n in eratSieve(N):
        if n not in known_primes:
            print N,n

Answer 3

def primes(N):
    primes = [x for x in (2, 3, 5, 7, 11, 13) if x < N]
    if N < 17: return primes
    candidators = [x for x in xrange((N - 2) | 1, 15, -2)
                    if x % 3 and x % 5 and x % 7 and x % 11 and x % 13]
    top = int(N ** 0.5)
    while (top + 1) * (top + 1) <= N: top += 1
    while True:
        p = candidators.pop()
        primes.append(p)
        if p > top: break
        candidators = filter(p.__rmod__, candidators)
    candidators.reverse()
    primes.extend(candidators)
    return primes

Ich denke, dieser Code würde schneller funktionieren...