Today is the birthday of Bernhard Riemann, a German mathematician who made fundamental contributions to the fields of geometry, analysis, and number theory. Riemann is definitely on my list of the greatest mathematicians of all time, and his conjecture about the distribution of prime numbers is one of the great unsolved problems in mathematics.
In honor of Riemann's birthday, this post deals with prime numbers.
One of the first mathematical algorithms that I learned as a kid is the “prime number sieve." (There is an animation of this algorithm in the Wikipedia article.) This algorithm is attributed to Eratosthenes, a mathematician from ancient Greece, and has been implemented in many programming languages. It is the only algorithm that I know of that has a poem written about it:
Sift the twos and sift the threes...,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are prime.
In celebration of Riemann’s birthday, I present the Sieve of Eratosthenes in the SAS/IML language:
/** The Sieve of Eratosthenes **/ proc iml; max = 200; list = 2:max; /** find prime numbers in [2, max] **/ primes = j(1, ncol(list), .); /** allocate space to store primes **/ numPrimes = 0; p = list; /** 2 is the first prime **/ do while (p##2 <= max); /** search through sqrt(max) **/ idx = loc( mod(list, p)=0 );/** find all numbers divisible by p **/ list = remove(list, idx); /** remove them. They are not prime. **/ numPrimes = numPrimes + 1; primes[numPrimes] = p; /** include p in the list of primes **/ p = list; /** next prime number to sift **/ end; /** include remaining numbers greater than sqrt(max) **/ k = numPrimes; n = k + ncol(list); primes[k+1:n] = list; /** put them at the end of the list **/ primes = primes[ ,1:n]; /** get rid of excess storage space **/
The following table shows the prime numbers less than two hundred that are found by the algorithm:
|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|
Do YOU have a classic algorithm or technique that you have implemented in the SAS/IML language? (Poems are optional.)