Primality Testing and Sieves

Math 242 Modern Computational Math

Basic prime testing

Mathematica has a slew of built-in tools for working with prime numbers. The most basic of these is PrimeQ, which returns True or False depending on whether the argument in prime number (or not). For example:

PrimeQ[17]
PrimeQ[33]

Your first task is to write your own function, myPrimeQ, which does the same thing (but doesn’t use Mathematica’s built-in PrimeQ). Here are the specifications for your function:

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

For example:
	myPrimeQ[11] ⟶ True
	myPrimeQ[12] ⟶ False

To develop the algorithm, think about how to determine if a number is prime using basic arithmetic. You can use any the Mathematica functions related to arithmetic and basic number theory. For example, Divisible[n, k] determines if the integer k divides the integer n.

Listing the Primes

Your second task is to use your new function, myPrimeQ, to build a function myPrimes that will create a list of all primes up to some value n.

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

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

Runtime

How efficient is your function? Find the runtime of your function for several choices of n. Make a plot of the time to compute this list. Potential values to test include n=(2^k) for k=1,2,3,.... Hint: Use ListPlot or ListLinePlot.

Based on your data, about how long would your function take to compute all the primes less than 1,000,000,000?

Sieve of Eratosthenes

The Sieve of Eratosthenes starts with a big list of numbers 2,3,4,...,n. The algorithm marks 2 as prime, and then marks all multiples of 2 as composite. Then the algorithm iteratively marks the next unmarked number as prime, and all of its multiples as composite.

Implement the Sieve of Eratosthenes.

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

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

Runtime

Analyze the time required to compute primes up to n using sieveErat. How does it compare with your previous method?