Prime Sieves

Math 242 Modern Computational Math

Sieve of Eratosthenes

Implementation 1

Here is a simple implementation of the Sieve of Eratosthenes.

sieveErat1[n_Integer]:=Module[
{nums=Range[2,n], (* we will remove composite numbers from this list as we find them *)
i=1, (* index of d, the number whose multiples we want to remove *)
j            (* index of the number we are testing to see if it is a multiple of d *)
},

While[nums[[i]]≤Sqrt[n], (* remove multiples of nums[[i]] *)
j=i+1;
While[j≤Length[nums],
If[Divisible[nums[[j]],nums[[i]]],nums=Delete[nums,j],j++]
];

(* testing: print the list *)
(*Print["removed ",nums[[i]],": ",nums];*)

i++
];
nums (* return the list, which now only contains primes *)
]

Try it out:

sieveErat1[100]

This works, but it’s awkward to have to keep track of two indexes, i and j. Also, the divisibility testing should be unnecessary: when doing the Sieve of Eratosthenes by hand, we never test for divisibility; we just cross off every dth number in the list.

Implementation 2

This implementation uses a list of Boolean values, indexed 1 to n, that all start out True. We don’t remove values from the list, but if we determine that a number k is composite, then we set the value at index k to False. At the end, we select the indexes greater than 1 that have value True, which give us the primes.

sieveErat2[n_Integer]:=Module[{m=Floor[Sqrt[n]],boolVals=Table[True,n]},
Do[
(* mark False all multiples of i *)
If[boolVals[[i]], boolVals[[i^2;;n;;i]]=False],
{i,2,m}];

(* select all indexes greater than 1 whose values are still True *)
Select[Range[2,n], (boolVals[[#]] &)]
]

Test it out:

sieveErat2[100]

How fast is it? Compare with the previous method.

Timing[sieveErat1[100000]][[1]]

Timing[sieveErat2[1000000]][[1]]

Implementation 3

Here is another implementation idea: Start with a list of positive integers from 1 to n. Instead of removing non-primes, set them to zero. When finished, select all nonzero elements. Write this implementation, and see how its runtime compares to your other implementations.

sieveErat3[n_Integer]:=Module[{m=Floor[Sqrt[n]],vals=Range[n]},
Do[
(* if vals[[i]] is not zero, then sete all multiples of i to zero *)
If[vals[[i]]≠0, vals[[i^2;;n;;i]]=0],
{i,2,m}];

(* select all indexes greater than 1 whose values are still True *)
Select[Range[2,n], (vals[[#]]≠0 &)]
]

Timing[sieveErat3[1000000]][[1]]

Sieve of Sundaram

Start with the list of integers 1,2,...,n. For every pair of integers (i,j) satisfying 1≤i≤j and i+j+2ij≤n, remove the number i+j+2ij from the list. Take all the numbers still in the list: double them and add 1 to each. This results in a list of all the odd primes below 2n+2.

Implement the Sieve of Sundaram.

sieveSund:
	Argument: an integer n
	Return: a list of primes less than or equal to 2n+2

For example:  sieveSund[20] ⟶ {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}

Runtime

How does the runtime of the Sieve of Sundaram compare with the runtime of the Sieve of Eratosthenes?

Fermat’s Conjecture

Fermat conjectured that all numbers of the form (2^(2^n))+1 are prime. For example, (2^(2^1))+1=4+1=5 is prime, and so is (2^(2^2))+1=(2^4)+1=17. Investigate Fermat’s conjecture for other values of n. Are all such numbers prime?