Prime number sieveA prime sieve creates all the prime numbers up to a given limit. It progressively removes composite numbers until it only has prime numbers left, and it is the most efficient way to generate a range of prime numbers: |
Code
The following is the Python equivalent code:
import sys test=1000 if (len(sys.argv)>1): test=int(sys.argv[1]) def sieve_for_primes_to(n): size = n//2 sieve = [1]*size limit = int(n**0.5) for i in range(1,limit): if sieve[i]: val = 2*i+1 tmp = ((size-1) - i)//val sieve[i+val::val] = [0]*tmp return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0] print (sieve_for_primes_to(test))
This works because we start with all the odd numbers up to the square root of the limit of the numbers we are looking for. If we have 100, then the size will be 50. We start off with odd numbers (as 2 is the only even prime):
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 .. 99
In the first time round we have i equal to 1, and we will jump 3 each time and mark them as not prime (to find all the factors of 3):
3 5 7911 131517 192123 252729 313335 .. 9799
In the next time round, we will jump 5, starting at 5 (to find all the factors of 5):
3 5 7 X 11 13X17 19 X 2325X 29 31 X35.. 97, X
In the next time round, we will jump 7, starting at 7 (to find all the factors of 7):
3 5 7 X 11 13 X 17 19X23 X X 29 31 XX.. 97 99
In the next time round, we will jump 9, starting at 9 (to find all the factors of 9):
3 5 7 X 11 13 X 17 19 X 23 XX29 31 X X .. 97 99
In the end we stop at 19, and with a jump of 19, and add the value of 2 to the discovered prime numbers:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97The marking of the factors follows this sequence:
[1, 3, 5, 7, 9, 11,13,15,17,19,21,23,25,27,29,31,33,35 .. ] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]