Fastest way to list all primes below N

Question

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   gt  gt  gt  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    gt  gt  gt  sum get primes 2000000   142913828922L  That s the correct sum of all numbers below 2 million  gt  gt  gt  529 in get primes 1000  False  gt  gt  gt  529 in get primes 530  True

User · Answer

This is an elegant and simpler solution to find primes using a stored list  Starts with a 4 variables  you only have to test odd primes for divisors  and you only have to test up to a half of what number you are testing as a prime  no point in testing whether 9  11  13 divide into 17   It tests previously stored primes as divisors          Program to calculate Primes  primes    1 3 5 7  for n in range 9 100000 2       for x in range 1  len primes  2            if n   primes x     0              break     else          primes append n  print primes

User · Answer

Here is an interesting technique to generate prime numbers  yet not the most efficient  using python s list comprehensions   noprimes    j for i in range 2  8  for j in range i 2  50  i   primes    x for x in range 2  50  if x not in noprimes    You can find the example and some explanations right here

User · Answer

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  from bitarray import bitarray def primes to n       size   n  2     sieve   bitarray size      sieve setall 1      limit   int n  0 5      for i in range 1 limit           if sieve i               val   2 i 1             sieve  i i val   val    0     return  2     2 i 1 for i  v in enumerate sieve  if v and i  gt  0   python -m timeit -n10 -s  import euler   euler primes to 1000000000   10 loops  best of 3  46 5 sec per loop   This was run on a 64bit 2 4GHZ MAC OSX 10 8 3

User · Answer

Faster  amp  more memory-wise pure Python code   def primes n           Returns  a list of primes  lt  n         sieve    True    n     for i in range 3 int n  0 5  1 2           if sieve i               sieve i i  2 i   False    n-i i-1    2 i  1      return  2     i for i in range 3 n 2  if sieve i     or starting with half sieve  def primes1 n           Returns  a list of primes  lt  n         sieve    True     n  2      for i in range 3 int n  0 5  1 2           if sieve i  2               sieve i i  2  i     False      n-i i-1    2 i  1      return  2     2 i 1 for i in range 1 n  2  if sieve i     Faster  amp  more memory-wise numpy code   import numpy def primesfrom3to n           Returns a array of primes  3  lt   p  lt  n         sieve   numpy ones n  2  dtype numpy bool      for i in range 3 int n  0 5  1 2           if sieve i  2               sieve i i  2  i    False     return 2 numpy nonzero sieve  0  1    1   a faster variation starting with a third of a sieve   import numpy def primesfrom2to n           Input n gt  6  Returns a array of primes  2  lt   p  lt  n         sieve   numpy ones n  3    n 6  2   dtype numpy bool      for i in range 1 int n  0 5   3 1           if sieve i               k 3 i 1 1             sieve        k k  3       2 k    False             sieve k  k-2  i amp 1  4   3  2 k    False     return numpy r  2 3   3 numpy nonzero sieve  0  1   1  1     A  hard-to-code  pure-python version of the above code would be   def primes2 n           Input n gt  6  Returns a list of primes  2  lt   p  lt  n         n  correction   n-n 6 6  2- n 6 gt 1      sieve    True     n  3      for i in range 1 int n  0 5   3 1         if sieve i           k 3 i 1 1         sieve       k k  3        2 k     False      n  6-k k  6-1   k 1          sieve k  k-2  i amp 1  4   3  2 k     False      n  6-k  k-2  i amp 1  4   6-1   k 1      return  2 3     3 i 1 1 for i in range 1 n  3-correction  if sieve i     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   amp  avoid more math  and do some extreme   amp  painful  math-magic     Personally I think it is a shame that numpy  which is so widely used  is not part of Python standard library  and that the improvements in syntax and speed seem to be completely overlooked by Python developers

User · Answer

A slightly different implementation of a half sieve using Numpy   http   rebrained com  p 458   import math import numpy def prime6 upto       primes numpy arange 3 upto 1 2      isprime numpy ones  upto-1  2 dtype bool      for factor in primes  int math sqrt upto             if isprime  factor-2  2   isprime  factor 3-2  2  upto-1  2 factor  0     return numpy insert primes isprime  0 2    Can someone compare this with the other timings   On my machine it seems pretty comparable to the other Numpy half-sieve

User · Answer

My guess is that the fastest of all ways is to hard code the primes in your code   So why not just write a slow script that generates another source file that has all numbers hardwired in it  and then import that source file when you run your actual program   Of course  this works only if you know the upper bound of N at compile time  but thus is the case for  almost  all project Euler problems     nbsp   PS  I might be wrong though iff parsing the source with hard-wired primes is slower than computing them in the first place  but as far I know Python runs from compiled  pyc files so reading a binary array with all primes up to N should be bloody fast in that case

User · Answer

Using Sundaram s Sieve  I think I broke pure-Python s record   def sundaram3 max n       numbers   range 3  max n 1  2      half    max n   2     initial   4      for step in xrange 3  max n 1  2           for i in xrange initial  half  step               numbers i-1    0         initial    2  step 1           if initial  gt  half              return  2    filter None  numbers    Comparasion   C  USERS gt python -m timeit -n10 -s  import get primes   get primes get primes erat 1000000   10 loops  best of 3  710 msec per loop  C  USERS gt python -m timeit -n10 -s  import get primes   get primes daniel sieve 2 1000000   10 loops  best of 3  435 msec per loop  C  USERS gt python -m timeit -n10 -s  import get primes   get primes sundaram3 1000000   10 loops  best of 3  327 msec per loop

User · Answer

A deterministic implementation of Miller-Rabin s Primality test on the assumption that N  lt  9 080 191  import sys import random  def miller rabin pass a  n       d   n - 1     s   0     while d   2    0          d  gt  gt   1         s    1      a to power   pow a  d  n      if a to power    1          return True     for i in xrange s-1           if a to power    n - 1              return True         a to power    a to power   a to power    n     return a to power    n - 1   def miller rabin n       for a in  2  3  37  73         if not miller rabin pass a  n           return False     return True   n   int sys argv 1   primes    2  for p in range 3 n 2     if miller rabin p       primes append p  print len primes    According to the article on Wikipedia  http   en wikipedia org wiki Miller   Rabin primality test  testing N  lt  9 080 191 for a   2 3 37  and 73 is enough to decide whether N is composite or not   And I adapted the source code from the probabilistic implementation of original Miller-Rabin s test found here  http   en literateprograms org Miller-Rabin primality test  Python

User · Answer

For truly fastest solution with sufficiently large N would be to download a pre-calculated list of primes  store it as a tuple and do something like   for pos i in enumerate primes       if i  gt  N          print primes  pos    If N  gt  primes -1  only then calculate more primes and save the new list in your code  so next time it is equally as fast   Always think outside the box

User · Answer

The fastest method I ve tried so far is based on the Python cookbook erat2 function   import itertools as it def erat2a         D            yield 2     for q in it islice it count 3   0  None  2           p   D pop q  None          if p is None              D q q    q             yield q         else              x   q   2 p             while x in D                  x    2 p             D x    p   See this answer for an explanation of the speeding-up

User · Answer

I know the competition is closed for some years       Nonetheless this is my suggestion for a pure python prime sieve  based on omitting the multiples of 2  3 and 5 by using appropriate steps while processing the sieve forward  Nonetheless it is actually slower for N lt 10 9 than  Robert William Hanks superior solutions rwh primes2 and rwh primes1  By using a ctypes c ushort sieve array above 1 5  10 8 it is somehow adaptive to memory limits   10 6    python -mtimeit -s import primeSieveSpeedComp   primeSieveSpeedComp primeSieveSeq 1000000   10 loops  best of 3  46 7 msec per loop     to compare   python -mtimeit -s import primeSieveSpeedComp     primeSieveSpeedComp rwh primes1 1000000   10 loops  best of 3  43 2   msec per loop   to compare    python -m timeit -s import primeSieveSpeedComp     primeSieveSpeedComp rwh primes2 1000000   10 loops  best of 3  34 5   msec per loop   10 7    python -mtimeit -s import primeSieveSpeedComp   primeSieveSpeedComp primeSieveSeq 10000000   10 loops  best of 3  530 msec per loop     to compare   python -mtimeit -s import primeSieveSpeedComp     primeSieveSpeedComp rwh primes1 10000000   10 loops  best of 3  494   msec per loop   to compare    python -m timeit -s import primeSieveSpeedComp     primeSieveSpeedComp rwh primes2 10000000   10 loops  best of 3  375   msec per loop   10 8    python -mtimeit -s import primeSieveSpeedComp   primeSieveSpeedComp primeSieveSeq 100000000   10 loops  best of 3  5 55 sec per loop     to compare    python -mtimeit -s import primeSieveSpeedComp     primeSieveSpeedComp rwh primes1 100000000   10 loops  best of 3  5 33   sec per loop   to compare    python -m timeit -s import primeSieveSpeedComp     primeSieveSpeedComp rwh primes2 100000000   10 loops  best of 3  3 95   sec per loop   10 9    python -mtimeit -s import primeSieveSpeedComp   primeSieveSpeedComp primeSieveSeq 1000000000   10 loops  best of 3  61 2 sec per loop     to compare    python -mtimeit -n 3 -s import primeSieveSpeedComp     primeSieveSpeedComp rwh primes1 1000000000   3 loops  best of 3  97 8   sec per loop      to compare    python -m timeit -s import primeSieveSpeedComp     primeSieveSpeedComp rwh primes2 1000000000   10 loops  best of 3    41 9 sec per loop   You may copy the code below into ubuntus primeSieveSpeedComp to review this tests   def primeSieveSeq MAX Int       if MAX Int  gt  5 10  8          import ctypes         int16Array   ctypes c ushort    MAX Int  gt  gt  1          sieve   int16Array            print  uses ctypes  unsigned short int Array       else          sieve    MAX Int  gt  gt  1     False           print  uses python list   of long long int      if MAX Int  lt  10  8          sieve 4  3     True    MAX Int - 8  6 1          sieve 12  5     True    MAX Int - 24  10 1      r    2  3  5      n   0     for i in xrange int MAX Int  0 5  30 1           n    3         if not sieve n               n2    n  lt  lt  1    1             r append n2              n2q    n2  2   gt  gt  1             sieve n2q  n2     True     MAX Int  gt  gt  1  - n2q - 1    n2   1          n    2         if not sieve n               n2    n  lt  lt  1    1             r append n2              n2q    n2  2   gt  gt  1             sieve n2q  n2     True     MAX Int  gt  gt  1  - n2q - 1    n2   1          n    1         if not sieve n               n2    n  lt  lt  1    1             r append n2              n2q    n2  2   gt  gt  1             sieve n2q  n2     True     MAX Int  gt  gt  1  - n2q - 1    n2   1          n    2         if not sieve n               n2    n  lt  lt  1    1             r append n2              n2q    n2  2   gt  gt  1             sieve n2q  n2     True     MAX Int  gt  gt  1  - n2q - 1    n2   1          n    1         if not sieve n               n2    n  lt  lt  1    1             r append n2              n2q    n2  2   gt  gt  1             sieve n2q  n2     True     MAX Int  gt  gt  1  - n2q - 1    n2   1          n    2         if not sieve n               n2    n  lt  lt  1    1             r append n2              n2q    n2  2   gt  gt  1             sieve n2q  n2     True     MAX Int  gt  gt  1  - n2q - 1    n2   1          n    3         if not sieve n               n2    n  lt  lt  1    1             r append n2              n2q    n2  2   gt  gt  1             sieve n2q  n2     True     MAX Int  gt  gt  1  - n2q - 1    n2   1          n    1         if not sieve n               n2    n  lt  lt  1    1             r append n2              n2q    n2  2   gt  gt  1             sieve n2q  n2     True     MAX Int  gt  gt  1  - n2q - 1    n2   1      if MAX Int  lt  10  8          return  2  3  5    p  lt  lt  1    1 for p in  n for n in xrange 3  MAX Int  gt  gt  1  if not sieve n        n   n  gt  gt  1     try          for i in xrange  MAX Int-2 n  30   1               n    3             if not sieve n                   r append  n  lt  lt  1    1              n    2             if not sieve n                   r append  n  lt  lt  1    1              n    1             if not sieve n                   r append  n  lt  lt  1    1              n    2             if not sieve n                   r append  n  lt  lt  1    1              n    1             if not sieve n                   r append  n  lt  lt  1    1              n    2             if not sieve n                   r append  n  lt  lt  1    1              n    3             if not sieve n                   r append  n  lt  lt  1    1              n    1             if not sieve n                   r append  n  lt  lt  1    1      except          pass     return r

User · Answer

First time using python  so some of the methods I use in this might seem a bit cumbersome  I just straight converted my c   code to python and this is what I have  albeit a tad bit slowww in python      usr bin env python import time  def GetPrimes n        Sieve    1 for x in xrange n        Done   False     w   3      while not Done           for q in xrange  3  n  2               Prod   w q             if Prod  lt  n                  Sieve Prod    0             else                  break          if w  gt   n 2               Done   True         w    2      return Sieve    start   time clock    d   10000000 Primes   GetPrimes d   count   1  This is for 2  for x in xrange  3  d  2       if Primes x           count  1  elapsed    time clock   - start  print   nFound   count   primes in   elapsed   seconds  n       pythonw Primes py      Found 664579 primes in 12 799119 seconds       usr bin env python import time  def GetPrimes2 n        Sieve    1 for x in xrange n        for q in xrange  3  n  2           k   q         for y in xrange k 3  n  k 2               Sieve y    0      return Sieve    start   time clock    d   10000000 Primes   GetPrimes2 d   count   1  This is for 2  for x in xrange  3  d  2       if Primes x           count  1  elapsed    time clock   - start  print   nFound   count   primes in   elapsed   seconds  n       pythonw Primes2 py      Found 664579 primes in 10 230172 seconds       usr bin env python import time  def GetPrimes3 n        Sieve    1 for x in xrange n        for q in xrange  3  n  2           k   q         for y in xrange k k  n  k  lt  lt  1               Sieve y    0      return Sieve    start   time clock    d   10000000 Primes   GetPrimes3 d   count   1  This is for 2  for x in xrange  3  d  2       if Primes x           count  1  elapsed    time clock   - start  print   nFound   count   primes in   elapsed   seconds  n       python Primes2 py      Found 664579 primes in 7 113776 seconds

User · Answer

If you accept itertools but not numpy  here is an adaptation of rwh primes2 for Python 3 that runs about twice as fast on my machine   The only substantial change is using a bytearray instead of a list for the boolean  and using compress instead of a list comprehension to build the final list    I d add this as a comment like moarningsun if I were able    import itertools izip   itertools zip longest chain   itertools chain from iterable compress   itertools compress def rwh primes2 python3 n           Input n gt  6  Returns a list of primes  2  lt   p  lt  n         zero   bytearray  False       size   n  3    n   6    2      sieve   bytearray  True     size     sieve 0    False     for i in range int n  0 5   3 1         if sieve i           k 3 i 1 1         start    k k 4 k-2 k  i amp 1    3         sieve  k k   3  2 k  zero   size -  k k   3 - 1      2   k    1          sieve   start   2 k  zero   size -   start  - 1      2   k    1      ans    2 3      poss   chain izip   range i  n  6  for i in  1 5         ans extend compress poss  sieve       return ans   Comparisons    gt  gt  gt  timeit timeit  primes rwh primes2 10  6    setup  import primes   number 1  0 0652179726976101  gt  gt  gt  timeit timeit  primes rwh primes2 python3 10  6    setup  import primes   number 1  0 03267321276325674   and   gt  gt  gt  timeit timeit  primes rwh primes2 10  8    setup  import primes   number 1  6 394284538007014  gt  gt  gt  timeit timeit  primes rwh primes2 python3 10  8    setup  import primes   number 1  3 833829450302801

User · Answer

It s all written and tested  So there is no need to reinvent the wheel   python -m timeit -r10 -s from sympy import sieve   primes   list sieve primerange 1  10  6      gives us a record breaking 12 2 msec   10 loops  best of 10  12 2 msec per loop   If this is not fast enough  you can try PyPy   pypy -m timeit -r10 -s from sympy import sieve   primes   list sieve primerange 1  10  6      which results in   10 loops  best of 10  2 03 msec per loop   The answer with 247 up-votes lists 15 9 ms for the best solution  Compare this

User · Answer

For Python 3  def rwh primes2 n       correction    n 6 gt 1      n    0 n 1 n-1 2 n 4 3 n 3 4 n 2 5 n 1  n 6      sieve    True     n  3      sieve 0    False     for i in range int n  0 5   3 1         if sieve i           k 3 i 1 1         sieve         k k   3         2 k   False    n  6- k k   6-1   k 1          sieve  k k 4 k-2 k  i amp 1    3  2 k   False    n  6- k k 4 k-2 k  i amp 1    6-1   k 1      return  2 3     3 i 1 1 for i in range 1 n  3-correction  if sieve i

User · Answer

There s a pretty neat sample from the Python Cookbook here -- the fastest version proposed on that URL is   import itertools def erat2         D            yield 2     for q in itertools islice itertools count 3   0  None  2           p   D pop q  None          if p is None              D q q    q             yield q         else              x   p   q             while x in D or not  x amp 1                   x    p             D x    p   so that would give  def get primes erat n     return list itertools takewhile lambda p  p lt n  erat2       Measuring at the shell prompt  as I prefer to do  with this code in pri py  I observe     python2 5 -mtimeit -s import pri   pri get primes 1000000   10 loops  best of 3  1 69 sec per loop   python2 5 -mtimeit -s import pri   pri get primes erat 1000000   10 loops  best of 3  673 msec per loop   so it looks like the Cookbook solution is over twice as fast

User · Answer

Here s the code I normally use to generate primes in Python     python -mtimeit -s import sieve   sieve sieve 1000000    10 loops  best of 3  445 msec per loop   cat sieve py from math import sqrt  def sieve size    prime  True  size  rng xrange  limit int sqrt size     for i in rng 3 limit 1  2     if prime i      prime i i   i   False  len prime i i   i     return  2   i for i in rng 3 size  2  if prime i    if   name       main      print sieve 100    It can t compete with the faster solutions posted here  but at least it is pure python   Thanks for posting this question  I really learnt a lot today

User · Answer

I collected several prime number sieves over time  The fastest on my computer is this   from time import time   175 ms for all the primes up to the value 10  6 def primes sieve limit       a    True    limit     a 0    a 1    False      a 2    True     for n in xrange 4  limit  2           a n    False     root limit   int limit   5  1     for i in xrange 3 root limit           if a i               for n in xrange i i  limit  2 i                   a n    False     return a  LIMIT   10  6 s time   primes   primes sieve LIMIT  print time  -s

User · Answer

It s instructive to write your own prime finding code  but it s also useful to have a fast reliable library at hand  I wrote a wrapper around the C   library primesieve  named it primesieve-python  Try it pip install primesieve  import primesieve primes   primesieve generate primes 10  8    I d be curious to see the speed compared

User · Answer

I ve updated much of the code for Python 3 and threw it at perfplot  a project of mine  to see which is actually fastest  Turns out that  for large n  primesfrom 2 3 to takes the cake    Code to reproduce the plot  import perfplot from math import sqrt  ceil import numpy as np import sympy   def rwh primes n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188      quot  quot  quot  Returns  a list of primes  lt  n  quot  quot  quot      sieve    True    n     for i in range 3  int n    0 5    1  2           if sieve i               sieve i   i  2   i     False      n - i   i - 1      2   i    1      return  2     i for i in range 3  n  2  if sieve i     def rwh primes1 n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188      quot  quot  quot  Returns  a list of primes  lt  n  quot  quot  quot      sieve    True     n    2      for i in range 3  int n    0 5    1  2           if sieve i    2               sieve i   i    2  i     False      n - i   i - 1      2   i    1      return  2     2   i   1 for i in range 1  n    2  if sieve i     def rwh primes2 n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188      quot  quot  quot Input n gt  6  Returns a list of primes  2  lt   p  lt  n quot  quot  quot      assert n  gt   6     correction   n   6  gt  1     n    0  n  1  n - 1  2  n   4  3  n   3  4  n   2  5  n   1  n   6      sieve    True     n    3      sieve 0    False     for i in range int n    0 5     3   1           if sieve i               k   3   i   1   1             sieve   k   k     3   2   k     False                       n    6 -  k   k     6 - 1     k   1                           sieve  k   k   4   k - 2   k    i  amp  1      3  2   k     False                       n    6 -  k   k   4   k - 2   k    i  amp  1      6 - 1     k   1                   return  2  3     3   i   1   1 for i in range 1  n    3 - correction  if sieve i     def sieve wheel 30 N         http   zerovolt com  p 88      quot  quot  quot  Returns a list of primes  lt   N using wheel criterion 2 3 5   30  Copyright 2009 by zerovolt com This code is free for non-commercial purposes  in which case you can just leave this comment as a credit for my work  If you need this code for commercial purposes  please contact me by sending an email to  info  at  zerovolt  dot  com  quot  quot  quot        smallp             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              wheel    2  3  5      const   30     if N  lt  2          return        if N  lt   const          pos   0         while   smallp pos   lt   N              pos    1         return list   smallp  pos         make the offsets list     offsets    7  11  13  17  19  23  29  1        prepare the list     p    2  3  5      dim   2   N    const     tk1    True    dim     tk7    True    dim     tk11    True    dim     tk13    True    dim     tk17    True    dim     tk19    True    dim     tk23    True    dim     tk29    True    dim     tk1 0    False       help dictionary d       d a   b    c     gt  if I want to find the smallest useful multiple of  30 pos  a       on tkc  then I need the index given by the product of   30 pos  a   30 pos  b        in general  If b  lt  a  I need   30 pos  a   30  pos 1   b      d          for x in offsets          for y in offsets              res    x   y    const             if res in offsets                  d  x  res     y       another help dictionary  gives tkx calling tmptk x      tmptk    1  tk1  7  tk7  11  tk11  13  tk13  17  tk17  19  tk19  23  tk23  29  tk29      pos  prime  lastadded  stop   0  0  0  int ceil sqrt N           inner functions definition     def del mult tk  start  step           for k in range start  len tk   step               tk k    False        end of inner functions definition     cpos   const   pos     while prime  lt  stop            30k   7         if tk7 pos               prime   cpos   7             p append prime              lastadded   7             for off in offsets                  tmp   d  7  off                   start                          pos   prime                      if off    7                     else  prime    const    pos   1 if tmp  lt  7 else 0    tmp      const                                   del mult tmptk off   start  prime            30k   11         if tk11 pos               prime   cpos   11             p append prime              lastadded   11             for off in offsets                  tmp   d  11  off                   start                          pos   prime                      if off    11                     else  prime    const    pos   1 if tmp  lt  11 else 0    tmp      const                                   del mult tmptk off   start  prime            30k   13         if tk13 pos               prime   cpos   13             p append prime              lastadded   13             for off in offsets                  tmp   d  13  off                   start                          pos   prime                      if off    13                     else  prime    const    pos   1 if tmp  lt  13 else 0    tmp      const                                   del mult tmptk off   start  prime            30k   17         if tk17 pos               prime   cpos   17             p append prime              lastadded   17             for off in offsets                  tmp   d  17  off                   start                          pos   prime                      if off    17                     else  prime    const    pos   1 if tmp  lt  17 else 0    tmp      const                                   del mult tmptk off   start  prime            30k   19         if tk19 pos               prime   cpos   19             p append prime              lastadded   19             for off in offsets                  tmp   d  19  off                   start                          pos   prime                      if off    19                     else  prime    const    pos   1 if tmp  lt  19 else 0    tmp      const                                   del mult tmptk off   start  prime            30k   23         if tk23 pos               prime   cpos   23             p append prime              lastadded   23             for off in offsets                  tmp   d  23  off                   start                          pos   prime                      if off    23                     else  prime    const    pos   1 if tmp  lt  23 else 0    tmp      const                                   del mult tmptk off   start  prime            30k   29         if tk29 pos               prime   cpos   29             p append prime              lastadded   29             for off in offsets                  tmp   d  29  off                   start                          pos   prime                      if off    29                     else  prime    const    pos   1 if tmp  lt  29 else 0    tmp      const                                   del mult tmptk off   start  prime            now we go back to top tk1  so we need to increase pos by 1         pos    1         cpos   const   pos           30k   1         if tk1 pos               prime   cpos   1             p append prime              lastadded   1             for off in offsets                  tmp   d  1  off                   start                          pos   prime                      if off    1                     else  prime    const   pos   tmp      const                                   del mult tmptk off   start  prime        time to add remaining primes       if lastadded    1  remove last element and start adding them from tk1       this way we don t need an  quot if quot  within the last while     if lastadded    1          p pop         now complete for every other possible prime     while pos  lt  len tk1           cpos   const   pos         if tk1 pos               p append cpos   1          if tk7 pos               p append cpos   7          if tk11 pos               p append cpos   11          if tk13 pos               p append cpos   13          if tk17 pos               p append cpos   17          if tk19 pos               p append cpos   19          if tk23 pos               p append cpos   23          if tk29 pos               p append cpos   29          pos    1       remove exceeding if present     pos   len p  - 1     while p pos   gt  N          pos -  1     if pos  lt  len p  - 1          del p pos   1          return p list     return p   def sieve of eratosthenes n        quot  quot  quot sieveOfEratosthenes n   return the list of the primes  lt  n  quot  quot  quot        Code from   lt dickinsm gmail com gt   Nov 30 2006       http   groups google com group comp lang python msg f1f10ced88c68c2d     if n  lt   2          return        sieve   list range 3  n  2       top   len sieve      for si in sieve          if si              bottom    si   si - 3     2             if bottom  gt   top                  break             sieve bottom  si     0    -  bottom - top     si      return  2     el for el in sieve if el    def sieve of atkin end        quot  quot  quot return a list of all the prime numbers  lt end using the Sieve of Atkin  quot  quot  quot        Code by Steve Krenzel   lt Sgk284 gmail com gt   improved       Code  https   web archive org web 20080324064651 http   krenzel info  p 83       Info  http   en wikipedia org wiki Sieve of Atkin     assert end  gt  0     lng    end - 1     2     sieve    False     lng   1       x max  x2  xd   int sqrt  end - 1    4 0    0  4     for xd in range 4  8   x max   2  8           x2    xd         y max   int sqrt end - x2           n  n diff   x2   y max   y max   y max  lt  lt  1  - 1         if not  n  amp  1               n -  n diff             n diff -  2         for d in range  n diff - 1   lt  lt  1  -1  -8               m   n   12             if m    1 or m    5                  m   n  gt  gt  1                 sieve m    not sieve m              n -  d      x max  x2  xd   int sqrt  end - 1    3 0    0  3     for xd in range 3  6   x max   2  6           x2    xd         y max   int sqrt end - x2           n  n diff   x2   y max   y max   y max  lt  lt  1  - 1         if not  n  amp  1               n -  n diff             n diff -  2         for d in range  n diff - 1   lt  lt  1  -1  -8               if n   12    7                  m   n  gt  gt  1                 sieve m    not sieve m              n -  d      x max  y min  x2  xd   int  2   sqrt 4 - 8    1 - end      4   -1  0  3     for x in range 1  x max   1           x2    xd         xd    6         if x2  gt   end              y min      int ceil sqrt x2 - end    - 1   lt  lt  1  - 2   lt  lt  1         n  n diff     x   x   x   lt  lt  1  - 1     x - 1   lt  lt  1  - 2   lt  lt  1         for d in range n diff  y min  -8               if n   12    11                  m   n  gt  gt  1                 sieve m    not sieve m              n    d      primes    2  3      if end  lt   3          return primes   max 0  end - 2        for n in range 5  gt  gt  1   int sqrt end     1   gt  gt  1           if sieve n               primes append  n  lt  lt  1    1              aux    n  lt  lt  1    1             aux    aux             for k in range aux  end  2   aux                   sieve k  gt  gt  1    False      s   int sqrt end     1     if s   2    0          s    1     primes extend  i for i in range s  end  2  if sieve i  gt  gt  1         return primes   def ambi sieve plain n       s   list range 3  n  2       for m in range 3  int n    0 5    1  2           if s  m - 3     2               for t in range  m   m - 3     2   n  gt  gt  1  - 1  m                   s t    0     return  2     t for t in s if t  gt  0    def sundaram3 max n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 2073279 2073279     numbers   range 3  max n   1  2      half    max n     2     initial   4      for step in range 3  max n   1  2           for i in range initial  half  step               numbers i - 1    0         initial    2    step   1           if initial  gt  half              return  2    filter None  numbers      Using Numpy  def ambi sieve n         http   tommih blogspot com 2009 04 fast-prime-number-generator html     s   np arange 3  n  2      for m in range 3  int n    0 5    1  2           if s  m - 3     2               s  m   m - 3     2  m    0     return np r  2  s s  gt  0     def primesfrom3to n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188      quot  quot  quot  Returns an array of primes  p  lt  n  quot  quot  quot      assert n  gt   2     sieve   np ones n    2  dtype np bool      for i in range 3  int n    0 5    1  2           if sieve i    2               sieve i   i    2  i    False     return np r  2  2   np nonzero sieve  0  1      1    def primesfrom2to n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188      quot  quot  quot  Input n gt  6  Returns an array of primes  2  lt   p  lt  n  quot  quot  quot      assert n  gt   6     sieve   np ones n    3    n   6    2   dtype np bool      sieve 0    False     for i in range int n    0 5     3   1           if sieve i               k   3   i   1   1             sieve   k   k     3   2   k    False             sieve  k   k   4   k - 2   k    i  amp  1      3  2   k    False     return np r  2  3    3   np nonzero sieve  0    1    1     def sympy sieve n       return list sympy sieve primerange 1  n     perfplot save       quot prime png quot       setup lambda n  n      kernels           rwh primes          rwh primes1          rwh primes2          sieve wheel 30          sieve of eratosthenes          sieve of atkin            ambi sieve plain            sundaram3          ambi sieve          primesfrom3to          primesfrom2to          sympy sieve             n range  2    k for k in range 3  25        logx True      logy True      xlabel  quot n quot

User · Answer

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   def erat3         from itertools import islice  count        q is the running integer that s checked for primeness        yield 2 and no other even number thereafter     yield 2     D            no need to mark D 4  as we will test odd numbers only     for q in islice count 3  0 None 2           if q in D                      is composite             p   D q              del D q                q is composite  p D q  is the first prime that               divides it  Since we ve reached q  we no longer               need it in the map  but we ll mark the next               multiple of its witnesses to prepare for larger               numbers              x   q   p p          next odd    multiple             while x in D         skip composites                 x    p p             D x    p         else                     is prime               q is a new prime                Yield it and mark its first multiple that isn t               already marked in previous iterations              D q q    q             yield q

User · Answer

For the fastest code  the numpy solution is the best  For purely academic reasons  though  I m posting my pure python version  which is a bit less than 50  faster than the cookbook version posted above  Since I make the entire list in memory  you need enough space to hold everything  but it seems to scale fairly well   def daniel sieve 2 maxNumber               Given a number  returns all numbers less than or equal to     that number which are prime              allNumbers   range 3  maxNumber 1  2      for mIndex  number in enumerate xrange 3  maxNumber 1  2            if allNumbers mIndex     0              continue           now set all multiples to 0         for index in xrange mIndex number   maxNumber-3  2 1  number               allNumbers index    0     return  2    filter lambda n  n  0  allNumbers    And the results    gt  gt  gt mine   timeit Timer  daniel sieve 2 1000000                            from sieves import daniel sieve 2    gt  gt  gt prev   timeit Timer  get primes erat 1000000                            from sieves import get primes erat    gt  gt  gt print  Mine   0 0 4f  ms  format min mine repeat 3  1   1000  Mine  428 9446 ms  gt  gt  gt print  Previous Best  0 0 4f  ms  format min prev repeat 3  1   1000  Previous Best 621 3581 ms

User · Answer

If you don t want to reinvent the wheel  you can install the symbolic maths library sympy  yes it s Python 3 compatible   pip install sympy   And use the primerange function  from sympy import sieve primes   list sieve primerange 1  10  6

User · Answer

This is the way you can compare with others     You have to list primes upto n nums   xrange 2  n  for i in range 2  10       nums   filter lambda s  s  i or s i  nums  print nums   So simple

User · Answer

If you have control over N  the very fastest way to list all primes is to precompute them  Seriously  Precomputing is a way overlooked optimization

User · Answer

I tested  some unutbu s functions  i computed it with hungred millions number  The winners are the functions that use numpy library    Note  It would also interesting make a memory utilization test       Sample code  Complete code on my github repository     usr bin env python  import lib import timeit import sys import math import datetime  import prettyplotlib as ppl import numpy as np  import matplotlib pyplot as plt from prettyplotlib import brewer2mpl  primenumbers gen          sieveOfEratosthenes        ambi sieve        ambi sieve plain        sundaram3        sieve wheel 30        primesfrom3to        primesfrom2to        rwh primes        rwh primes1        rwh primes2      def human format num         https   stackoverflow com questions 579310 formatting-long-numbers-as-strings-in-python answertab active tab-top     magnitude   0     while abs num   gt   1000          magnitude    1         num    1000 0       add more suffixes if you need them     return    2f s     num        K    M    G    T    P   magnitude     if   name       main            Vars     n   10000000   number itereration generator     nbcol   5   For decompose prime number generator     nb benchloop   3   Eliminate false positive value during the test  bench average time      datetimeformat     Y- m- d  H  M  S  f      config    from   main   import n  import lib      primenumbers gen              sieveOfEratosthenes     color    b             ambi sieve     color    b             ambi sieve plain     color    b              sundaram3     color    b             sieve wheel 30     color    b                  primesfrom2to     color    b             primesfrom3to     color    b               rwh primes     color    b               rwh primes1     color    b             rwh primes2     color    b                  Get n in command line     if len sys argv  gt 1          n   int sys argv 1        step   int math ceil n   float nbcol        nbs   np array  i   step for i in range 1  int nbcol    1        set2   brewer2mpl get map  Paired    qualitative   12  mpl colors      print datetime datetime now   strftime datetimeformat      print  Compute prime number to   n s    locals        print          results   dict       for pgen in primenumbers gen          results pgen    dict           benchtimes   list           for n in nbs              t   timeit Timer  lib   pgen s n     locals    setup config              execute times   t repeat repeat nb benchloop number 1              benchtime   np mean execute times              benchtimes append benchtime          results pgen      benchtimes  np array benchtimes    fig  ax   plt subplots 1  plt ylabel  Computation time  in second    plt xlabel  Numbers computed   i   0 for pgen in primenumbers gen       bench   results pgen   benchtimes       avgs   np divide bench nbs      avg   np average bench  weights nbs         Compute linear regression     A   np vstack  nbs  np ones len nbs     T     a  b   np linalg lstsq A  nbs avgs  0         Plot     i    1      label    pgen s    locals        ppl plot nbs  nbs avgs  label label  lw 1  linestyle  --   color set2 i   12       label    pgen s avg    locals       ppl plot nbs  a   nbs   b  label label  lw 2  color set2 i   12   print datetime datetime now   strftime datetimeformat   ppl legend ax  loc  upper left   ncol 4     Change x axis label ax get xaxis   get major formatter   set scientific False  fig canvas draw   labels    human format int item get text     for item in ax get xticklabels     ax set xticklabels labels  ax   plt gca    plt show

User · Answer

I m slow responding to this question but it seemed like a fun exercise  I m using numpy which might be cheating and I doubt this method is the fastest but it should be clear  It sieves a Boolean array referring to its indices only and elicits prime numbers from the indices of all True values  No modulo needed   import numpy as np def ajs primes3a upto       mat   np ones  upto   dtype bool      mat 0    False     mat 1    False     mat 4  2    False     for idx in range 3  int upto    0 5  1  2           mat idx 2  idx    False     return np where mat    True  0

User · Answer

The simplest way I ve found of doing this is   primes      for n in range low  high   1       if all n   i for i in primes           primes append n

User · Answer

Here is two updated  pure Python 3 6  versions of one of the fastest functions   from itertools import compress  def rwh primes1v1 n           Returns  a list of primes  lt  n for n  gt  2         sieve   bytearray  True      n  2      for i in range 3 int n  0 5  1 2           if sieve i  2               sieve i i  2  i    bytearray  n-i i-1    2 i  1      return  2  compress range 3 n 2   sieve 1      def rwh primes1v2 n           Returns a list of primes  lt  n for n  gt  2         sieve   bytearray  True      n  2 1      for i in range 1 int n  0 5   2 1           if sieve i               sieve 2 i  i 1   2 i 1    bytearray  n  2-2 i  i 1     2 i 1  1      return  2  compress range 3 n 2   sieve 1

User · Answer

Warning  timeit results may vary due to differences in hardware or version of Python     Below is a script which compares a number of implementations    ambi sieve plain  rwh primes   rwh primes1   rwh primes2   sieveOfAtkin   sieveOfEratosthenes   sundaram3  sieve wheel 30  ambi sieve  requires numpy  primesfrom3to  requires numpy  primesfrom2to  requires numpy    Many thanks to stephan for bringing sieve wheel 30 to my attention  Credit goes to Robert William Hanks for primesfrom2to  primesfrom3to  rwh primes  rwh primes1  and rwh primes2   Of the plain Python methods tested  with psyco  for n 1000000  rwh primes1 was the fastest tested    --------------------- -------    Method                ms       --------------------- -------    rwh primes1           43 0      sieveOfAtkin          46 4      rwh primes            57 4      sieve wheel 30        63 0      rwh primes2           67 8          sieveOfEratosthenes   147 0     ambi sieve plain      152 0     sundaram3             194 0    --------------------- -------    Of the plain Python methods tested  without psyco  for n 1000000  rwh primes2 was the fastest    --------------------- -------    Method                ms       --------------------- -------    rwh primes2           68 1      rwh primes1           93 7      rwh primes            94 6      sieve wheel 30        97 4      sieveOfEratosthenes   178 0     ambi sieve plain      286 0     sieveOfAtkin          314 0     sundaram3             416 0    --------------------- -------    Of all the methods tested  allowing numpy  for n 1000000  primesfrom2to was the fastest tested    --------------------- -------    Method                ms       --------------------- -------    primesfrom2to         15 9      primesfrom3to         18 4      ambi sieve            29 3     --------------------- -------    Timings were measured using the command   python -mtimeit -s import primes   primes  method  1000000     with  method  replaced by each of the method names   primes py      usr bin env python import psyco  psyco full   from math import sqrt  ceil import numpy as np  def rwh primes n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188         Returns  a list of primes  lt  n         sieve    True    n     for i in xrange 3 int n  0 5  1 2           if sieve i               sieve i i  2 i   False    n-i i-1   2 i  1      return  2     i for i in xrange 3 n 2  if sieve i    def rwh primes1 n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188         Returns  a list of primes  lt  n         sieve    True     n 2      for i in xrange 3 int n  0 5  1 2           if sieve i 2               sieve i i 2  i     False      n-i i-1   2 i  1      return  2     2 i 1 for i in xrange 1 n 2  if sieve i    def rwh primes2 n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188         Input n gt  6  Returns a list of primes  2  lt   p  lt  n         correction    n 6 gt 1      n    0 n 1 n-1 2 n 4 3 n 3 4 n 2 5 n 1  n 6      sieve    True     n 3      sieve 0    False     for i in xrange int n  0 5  3 1         if sieve i           k 3 i 1 1         sieve         k k  3         2 k   False    n 6- k k  6-1  k 1          sieve  k k 4 k-2 k  i amp 1   3  2 k   False    n 6- k k 4 k-2 k  i amp 1   6-1  k 1      return  2 3     3 i 1 1 for i in xrange 1 n 3-correction  if sieve i    def sieve wheel 30 N         http   zerovolt com  p 88         Returns a list of primes  lt   N using wheel criterion 2 3 5   30  Copyright 2009 by zerovolt com This code is free for non-commercial purposes  in which case you can just leave this comment as a credit for my work  If you need this code for commercial purposes  please contact me by sending an email to  info  at  zerovolt  dot  com           smallp     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       wheel    2  3  5      const   30     if N  lt  2          return        if N  lt   const          pos   0         while   smallp pos   lt   N              pos    1         return list   smallp  pos         make the offsets list     offsets    7  11  13  17  19  23  29  1        prepare the list     p    2  3  5      dim   2   N    const     tk1     True    dim     tk7     True    dim     tk11    True    dim     tk13    True    dim     tk17    True    dim     tk19    True    dim     tk23    True    dim     tk29    True    dim     tk1 0    False       help dictionary d       d a   b    c     gt  if I want to find the smallest useful multiple of  30 pos  a       on tkc  then I need the index given by the product of   30 pos  a   30 pos  b        in general  If b  lt  a  I need   30 pos  a   30  pos 1   b      d          for x in offsets          for y in offsets              res    x y    const             if res in offsets                  d  x  res     y       another help dictionary  gives tkx calling tmptk x      tmptk    1 tk1  7 tk7  11 tk11  13 tk13  17 tk17  19 tk19  23 tk23  29 tk29      pos  prime  lastadded  stop   0  0  0  int ceil sqrt N          inner functions definition     def del mult tk  start  step           for k in xrange start  len tk   step               tk k    False       end of inner functions definition     cpos   const   pos     while prime  lt  stop            30k   7         if tk7 pos               prime   cpos   7             p append prime              lastadded   7             for off in offsets                  tmp   d  7  off                   start    pos   prime  if off    7 else  prime    const    pos   1 if tmp  lt  7 else 0    tmp     const                 del mult tmptk off   start  prime            30k   11         if tk11 pos               prime   cpos   11             p append prime              lastadded   11             for off in offsets                  tmp   d  11  off                   start    pos   prime  if off    11 else  prime    const    pos   1 if tmp  lt  11 else 0    tmp     const                 del mult tmptk off   start  prime            30k   13         if tk13 pos               prime   cpos   13             p append prime              lastadded   13             for off in offsets                  tmp   d  13  off                   start    pos   prime  if off    13 else  prime    const    pos   1 if tmp  lt  13 else 0    tmp     const                 del mult tmptk off   start  prime            30k   17         if tk17 pos               prime   cpos   17             p append prime              lastadded   17             for off in offsets                  tmp   d  17  off                   start    pos   prime  if off    17 else  prime    const    pos   1 if tmp  lt  17 else 0    tmp     const                 del mult tmptk off   start  prime            30k   19         if tk19 pos               prime   cpos   19             p append prime              lastadded   19             for off in offsets                  tmp   d  19  off                   start    pos   prime  if off    19 else  prime    const    pos   1 if tmp  lt  19 else 0    tmp     const                 del mult tmptk off   start  prime            30k   23         if tk23 pos               prime   cpos   23             p append prime              lastadded   23             for off in offsets                  tmp   d  23  off                   start    pos   prime  if off    23 else  prime    const    pos   1 if tmp  lt  23 else 0    tmp     const                 del mult tmptk off   start  prime            30k   29         if tk29 pos               prime   cpos   29             p append prime              lastadded   29             for off in offsets                  tmp   d  29  off                   start    pos   prime  if off    29 else  prime    const    pos   1 if tmp  lt  29 else 0    tmp     const                 del mult tmptk off   start  prime            now we go back to top tk1  so we need to increase pos by 1         pos    1         cpos   const   pos           30k   1         if tk1 pos               prime   cpos   1             p append prime              lastadded   1             for off in offsets                  tmp   d  1  off                   start    pos   prime  if off    1 else  prime    const   pos   tmp     const                 del mult tmptk off   start  prime        time to add remaining primes       if lastadded    1  remove last element and start adding them from tk1       this way we don t need an  if  within the last while     if lastadded    1          p pop         now complete for every other possible prime     while pos  lt  len tk1           cpos   const   pos         if tk1 pos   p append cpos   1          if tk7 pos   p append cpos   7          if tk11 pos   p append cpos   11          if tk13 pos   p append cpos   13          if tk17 pos   p append cpos   17          if tk19 pos   p append cpos   19          if tk23 pos   p append cpos   23          if tk29 pos   p append cpos   29          pos    1       remove exceeding if present     pos   len p  - 1     while p pos   gt  N          pos -  1     if pos  lt  len p  - 1          del p pos 1         return p list     return p  def sieveOfEratosthenes n          sieveOfEratosthenes n   return the list of the primes  lt  n           Code from   lt dickinsm gmail com gt   Nov 30 2006       http   groups google com group comp lang python msg f1f10ced88c68c2d     if n  lt   2          return        sieve   range 3  n  2      top   len sieve      for si in sieve          if si              bottom    si si - 3     2             if bottom  gt   top                  break             sieve bottom  si     0    -  bottom - top     si      return  2     el for el in sieve if el   def sieveOfAtkin end          sieveOfAtkin end   return a list of all the prime numbers  lt end     using the Sieve of Atkin           Code by Steve Krenzel   lt Sgk284 gmail com gt   improved       Code  https   web archive org web 20080324064651 http   krenzel info  p 83       Info  http   en wikipedia org wiki Sieve of Atkin     assert end  gt  0     lng     end-1     2      sieve    False     lng   1       x max  x2  xd   int sqrt  end-1  4 0    0  4     for xd in xrange 4  8 x max   2  8           x2    xd         y max   int sqrt end-x2           n  n diff   x2   y max y max   y max  lt  lt  1  - 1         if not  n  amp  1               n -  n diff             n diff -  2         for d in xrange  n diff - 1   lt  lt  1  -1  -8               m   n   12             if m    1 or m    5                  m   n  gt  gt  1                 sieve m    not sieve m              n -  d      x max  x2  xd   int sqrt  end-1    3 0    0  3     for xd in xrange 3  6   x max   2  6           x2    xd         y max   int sqrt end-x2           n  n diff   x2   y max y max   y max  lt  lt  1  - 1         if not n  amp  1               n -  n diff             n diff -  2         for d in xrange  n diff - 1   lt  lt  1  -1  -8               if n   12    7                  m   n  gt  gt  1                 sieve m    not sieve m              n -  d      x max  y min  x2  xd   int  2   sqrt 4-8  1-end    4   -1  0  3     for x in xrange 1  x max   1           x2    xd         xd    6         if x2  gt   end  y min      int ceil sqrt x2 - end    - 1   lt  lt  1  - 2   lt  lt  1         n  n diff     x x   x   lt  lt  1  - 1     x-1   lt  lt  1  - 2   lt  lt  1         for d in xrange n diff  y min  -8               if n   12    11                  m   n  gt  gt  1                 sieve m    not sieve m              n    d      primes    2  3      if end  lt   3          return primes  max 0 end-2        for n in xrange 5  gt  gt  1   int sqrt end   1   gt  gt  1           if sieve n               primes append  n  lt  lt  1    1              aux    n  lt  lt  1    1             aux    aux             for k in xrange aux  end  2   aux                   sieve k  gt  gt  1    False      s    int sqrt end     1     if s    2    0          s    1     primes extend  i for i in xrange s  end  2  if sieve i  gt  gt  1         return primes  def ambi sieve plain n       s   range 3  n  2      for m in xrange 3  int n  0 5  1  2            if s  m-3  2                for t in xrange  m m-3  2  n gt  gt 1 -1 m                   s t  0     return  2   t for t in s if t gt 0   def sundaram3 max n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 2073279 2073279     numbers   range 3  max n 1  2      half    max n   2     initial   4      for step in xrange 3  max n 1  2           for i in xrange initial  half  step               numbers i-1    0         initial    2  step 1           if initial  gt  half              return  2    filter None  numbers                                                                                      Using Numpy  def ambi sieve n         http   tommih blogspot com 2009 04 fast-prime-number-generator html     s   np arange 3  n  2      for m in xrange 3  int n    0 5  1  2            if s  m-3  2                s  m m-3  2  m  0     return np r  2  s s gt 0    def primesfrom3to n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188         Returns a array of primes  p  lt  n         assert n gt  2     sieve   np ones n 2  dtype np bool      for i in xrange 3 int n  0 5  1 2           if sieve i 2               sieve i i 2  i    False     return np r  2  2 np nonzero sieve  0  1    1       def primesfrom2to n         https   stackoverflow com questions 2068372 fastest-way-to-list-all-primes-below-n-in-python 3035188 3035188         Input n gt  6  Returns a array of primes  2  lt   p  lt  n         sieve   np ones n 3    n 6  2   dtype np bool      sieve 0    False     for i in xrange int n  0 5  3 1           if sieve i               k 3 i 1 1             sieve         k k  3         2 k    False             sieve  k k 4 k-2 k  i amp 1   3  2 k    False     return np r  2 3   3 np nonzero sieve  0  1  1    if   name       main         import itertools     import sys      def test f1 f2 num           print  Testing  f1  and  f2  return same results  format              f1 f1 func name              f2 f2 func name           if not all  a  b for a b in itertools izip longest f1 num  f2 num                  sys exit  Error   s  s      s  s    f1 func name num f2 func name num        n 1000000     test sieveOfAtkin sieveOfEratosthenes n      test sieveOfAtkin ambi sieve n      test sieveOfAtkin ambi sieve plain n       test sieveOfAtkin sundaram3 n      test sieveOfAtkin sieve wheel 30 n      test sieveOfAtkin primesfrom3to n      test sieveOfAtkin primesfrom2to n      test sieveOfAtkin rwh primes n      test sieveOfAtkin rwh primes1 n               test sieveOfAtkin rwh primes2 n    Running the script tests that all implementations give the same result

User · Answer

This is a variation of the solution in the question that should be faster than what s in the question  It uses a static sieve of Eratosthenes with no other optimizations  from typing import List  def list primes limit  int  - gt  List int       primes   set range 2  limit   1       for i in range 2  limit   1           if i in primes              primes difference update set list range i  limit   1  i   1         return sorted primes    gt  gt  gt  list primes 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

User · Answer

Fastest prime sieve in Pure Python   from itertools import compress  def half sieve n               Returns a list of prime numbers less than  n               if n  lt   2          return        sieve   bytearray  True      n    2      for i in range 3  int n    0 5    1  2           if sieve i    2               sieve i   i    2  i    bytearray  n - i   i - 1      2   i    1      primes   list compress range 1  n  2   sieve       primes 0    2     return primes   I optimised Sieve of Eratosthenes for speed and memory    Benchmark  from time import clock import platform  def benchmark iterations  limit       start   clock       for x in range iterations           half sieve limit      end   clock   - start     print f  end iterations  4f  seconds for primes  lt   limit     if   name         main         print platform python version        print platform platform        print platform processor        it   10     for pw in range 4  9           benchmark it  10  pw    Output   gt  gt  gt  3 6 7  gt  gt  gt  Windows-10-10 0 17763-SP0  gt  gt  gt  Intel64 Family 6 Model 78 Stepping 3  GenuineIntel  gt  gt  gt  0 0003 seconds for primes  lt  10000  gt  gt  gt  0 0021 seconds for primes  lt  100000  gt  gt  gt  0 0204 seconds for primes  lt  1000000  gt  gt  gt  0 2389 seconds for primes  lt  10000000  gt  gt  gt  2 6702 seconds for primes  lt  100000000

User · Answer

The algorithm is fast  but it has a serious flaw    gt  gt  gt  sorted get primes 530    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  527  529   gt  gt  gt  17 31 527  gt  gt  gt  23 23 529   You assume that numbers pop   would return the smallest number in the set  but this is not guaranteed at all  Sets are unordered and pop   removes and returns an arbitrary element  so it cannot be used to select the next prime from the remaining numbers

User · Answer

I found a pure Python 2 prime generator here   in a comment by Willy Good  that is faster than rwh2 primes     def primes235 limit   yield 2  yield 3  yield 5 if limit  lt  7  return modPrms    7 11 13 17 19 23 29 31  gaps    4 2 4 2 4 6 2 6 4 2 4 2 4 6 2 6    2 loops for overflow ndxs    0 0 0 0 1 1 2 2 2 2 3 3 4 4 4 4 5 5 5 5 5 5 6 6 7 7 7 7 7 7  lmtbf    limit   23     30   8 - 1   integral number of wheels rounded up lmtsqrt    int limit    0 5  - 7  lmtsqrt   lmtsqrt    30   8   ndxs lmtsqrt   30    round down on the wheel buf    True     lmtbf   1  for i in xrange lmtsqrt   1       if buf i           ci   i  amp  7  p   30    i  gt  gt  3    modPrms ci          s   p   p - 7  p8   p  lt  lt  3         for j in range 8               c   s    30   8   ndxs s   30              buf c  p8     False      lmtbf - c     p8   1              s    p   gaps ci   ci    1 for i in xrange lmtbf - 6    ndxs  limit - 7    30       adjust for extras     if buf i   yield  30    i  gt  gt  3    modPrms i  amp  7     My results     time   prime rwh2 py 1e8 5761455 primes found  lt  1e8  real    0m3 201s user    0m2 609s sys     0m0 578s   time   prime wheel py 1e8 5761455 primes found  lt  1e8  real    0m2 710s user    0m2 469s sys     0m0 219s      on my recent midrange laptop  i5 8265U 1 6GHz  running Ubuntu on Win 10   This is a mod 30 wheel sieve which skips multiples of 2  3  and 5   It works great for me up to about 2 5e9  when my laptop starts running out of 8G RAM and swapping a lot     I like mod 30 since it has only 8 remainders that aren t multiples of 2  3  or 5  That enables using shifts and   amp   for multiplication  division and mod  and should allow packing results for one mod 30 wheel into a byte   I have morphed Willy s code into a segmented mod 30 wheel sieve to eliminate the thrashing for big N and posted it here   There is an even faster Javascript version which is segmented and uses a mod 210 wheel  no multiples of 2  3  5  or 7  by  GordonBGood with an in depth explanation that is useful to me

User · Answer

Here is a numpy version of Sieve of Eratosthenes having both good complexity  lower than sorting an array of length n  and vectorization   Compared to  unutbu times this just as fast as the packages with 46 microsecons to find all primes below a million    import numpy as np  def generate primes n       is prime   np ones n 1 dtype bool      is prime 0 2    False     for i in range int n  0 5  1           if is prime i               is prime i  2  i  False     return np where is prime  0    Timings    import time     for i in range 2 10       timer  time time       generate primes 10  i      print  n   10   i   time     round time time  -timer 6     gt  gt  n   10  2  time   5 6e-05  gt  gt  n   10  3  time   6 4e-05  gt  gt  n   10  4  time   0 000114  gt  gt  n   10  5  time   0 000593  gt  gt  n   10  6  time   0 00467  gt  gt  n   10  7  time   0 177758  gt  gt  n   10  8  time   1 701312  gt  gt  n   10  9  time   19 322478

[python] Fastest way to list all primes below N

Examples related to python

Examples related to math

Examples related to optimization

Examples related to primes