hab mich mal an der Implementierung in Python versucht.
Das ganze Skaliert nur sehr sehr schlecht, was natürlich auch am Algorithmus selbst liegen dürfte, aber vielleicht hängts auch am Code, drum hätt ich gerne ein paar Meinungen dazu
Code: Alles auswählen
def primeSieve(upperLimit):
"""
Use sieve of Erastothenes to determine the primes till upperLimit.
Returns a list
"""
#generate a dictionary of all odd numbers from 3 on, with default values of True
primeCandidateDict = dict.fromkeys(xrange(3, upperLimit+1, 2), True)
primeList = [2] #2 is a prime for sure
for prime in sorted(primeCandidateDict.keys()):
#remove all multiples of prime
if not primeCandidateDict[prime]: #Skip if prime's value is False
continue
for nonprime in xlrange(prime**2, upperLimit+1, prime):
if nonprime in primeCandidateDict:
primeCandidateDict[nonprime] = False
else:
continue
primeList.append(prime)
return primeList
€²: xlrange() siehe hier, danke für das nützliche Snippet