Prime numbers are one of the most interesting subsets of the integers. Today, I was asked to provide an algorithmic primality test in my Probability class, and I fought with the problem for several minutes. I of course thought of a naive algorithm to check each number between 2 and n – 1 for divisibility with n, but that just isn’t satisfying (or fast) enough. This really stimulated my thinking, and may have started a new obsession with primes.
One of the solutions presented by my professor was Wilson’s Theorem for testing primality:
if (n – 1)! + 1 % n = 0, then n is prime. However, the obvious problem with this is the factorial operator. That’s going to generate an extremely large number, extremely fast. It’s obviously ridiculously inefficient.
Another method presented was a probabilistic function attributed to Gauss for determining the probability that a given number is prime. I didn’t see it as being very useful, so I’ve forgotten it to make room for more important things.
I was incorrectly under the impression that finding primes was an unsolved problem, however, a little research showed that it was solved in 2002 by three brilliant Indian computer scientists. Their algorithm builds upon Fermat’s Little Theorem. I’m considering implementing it for use in my Probability class, since we seem to be finding primes and relative primes frequently.
Well, since that’s a solved problem, I’ve become interested in the ordering of the primes. I saw a neat gif image showing the Sieve of Eratosthenes in action; perhaps I’ll expand that into a Java applet to start. It will at least be entertaining.
