This is the best algorithm I could come up.
def get_primes(n):
numbers = set(range(n, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return primes
>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import get_primes').timeit(1)
1.1499958793645562
Can it be made even faster?
This code has a flaw: Since numbers
is an unordered set, there is no guarantee that numbers.pop()
will remove the lowest number from the set. Nevertheless, it works (at least for me) for some input numbers:
>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True
Using Sundaram's Sieve, I think I broke pure-Python's record:
Comparasion:
It's all written and tested. So there is no need to reinvent the wheel.
gives us a record breaking 12.2 msec!
If this is not fast enough, you can try PyPy:
which results in:
The answer with 247 up-votes lists 15.9 ms for the best solution. Compare this!!!
Sorry to bother but erat2() has a serious flaw in the algorithm.
While searching for the next composite, we need to test odd numbers only. q,p both are odd; then q+p is even and doesn't need to be tested, but q+2*p is always odd. This eliminates the "if even" test in the while loop condition and saves about 30% of the runtime.
While we're at it: instead of the elegant 'D.pop(q,None)' get and delete method use 'if q in D: p=D[q],del D[q]' which is twice as fast! At least on my machine (P3-1Ghz). So I suggest this implementation of this clever algorithm:
Related question(dealing with primes generators & including benchmarks):
Speed up bitstring/bit operations in Python?
For a python 3 versions using bytearray & compress see: https://stackoverflow.com/a/46635266/350331
Faster & more memory-wise pure Python code:
or starting with half sieve
Faster & more memory-wise numpy code:
a faster variation starting with a third of a sieve:
A (hard-to-code) pure-python version of the above code would be:
Unfortunately pure-python don't adopt the simpler and faster numpy way of doing Assignment, and calling len() inside the loop as in
[False]*len(sieve[((k*k)/3)::2*k])
is too slow. So i had to improvise to correct input (& avoid more math) and do some extreme (& painful) math-magic.Personally i think it is a shame that numpy (which is so widely used) is not part of python standard library(2 years after python 3 release & no numpy compatibility), and that the improvements in syntax and speed seem to be completely overlooked by python developers.
Here is two updated (pure Python 3.6) versions of one of the fastest functions,
I may be late to the party but will have to add my own code for this. It uses approximately n/2 in space because we don't need to store even numbers and I also make use of the bitarray python module, further draStically cutting down on memory consumption and enabling computing all primes up to 1,000,000,000
This was run on a 64bit 2.4GHZ MAC OSX 10.8.3