Primality Testing and Sieves

Math 242 Modern Computational Math

Primality testing by trial division

On Wednesday we wrote a function isPrime which tests whether a number is prime.

isPrime:
	Argument: an integer n
	Return: True if n is prime, False if n is not prime

Here is one possible implementation:

isPrime[n_]:=Module[{foundDivisor=False},
Do[
If[Divisible[n,k],foundDivisor=True],
{k,2,Sqrt[n]}
];

!foundDivisor  (* return value *)
];

Try it out:

isPrime/@{2,3,19,22,25,29}

This implementation isn’t very efficient, since the loop doesn’t stop when it finds a divisor.

A faster implementation:

Here, we use a while loop that stops when a divisor is found.

isPrime2[n_]:=Module[ {foundDivisor=False,d=2,m=Sqrt[n]},

While[!foundDivisor && d≤m,
If[Divisible[n,d],foundDivisor=True];
d++
];

!foundDivisor (* return value *)
]

Try it out:

isPrime2/@{2,3,19,22,25,29}

Note that this implementation is much faster than the previous when n has a small factor:

Timing[isPrime[44466501336146]]

Timing[isPrime2[44466501336146]]

A sophisticated implementation:

This implementation uses Throw to stop a Do loop when a divisor is found; in this case, the enclosing Catch takes the value False. If no divisor is found, then the Catch statement takes the value True when the loop finishes. The value of the Catch statement is also the value that the Module returns.

isPrime3[n_Integer]:=Module[{m=Sqrt[n]},
Catch[
Do[ 
If[Divisible[n,d],Throw[False]],
{d,2,m}
];
True
] (* the Module returns the "caught" value *)
]

Try it out:

isPrime3/@{2,3,19,22,25,29}

This is a bit faster than the previous implementation:

Timing[isPrime2[79009213931]]

Timing[isPrime3[79009213931]]

Listing the primes

Next we want to write a function listPrimes that will create a list of all primes up to some value n.

listPrimes:
	Argument: an integer n
	Return: a list of primes less than or equal to n

For example:  listPrimes[20] ⟶ {2, 3, 5, 7, 11, 13, 17, 19}

Here is the module framework. We just need to fill in the details.

listPrimes[n_]:=Module[{},


]