The Armchair Politician

I’ve officially entered in the search for prime numbers. A professor I’d had for Discrete Modeling, Dr. Joseph DeMaio, was looking for research assistants, and I signed up. As it turns out, he has some interesting theories for culling out numbers when searching for primes.

The biggest task in finding primes isn’t calculating whether or not a number is prime. This, actually, is the easiest part. Unfortunately, it’s fairly processor-intensive to do so. Thus, when you start trying to do the calculations for each and every number, the time involved is massive. The trick is trying to find easy ways for determining that numbers aren’t prime. For instance, we know that every even number is composite. So are any numbers where the sum of its digits are a multiple of three. However, this is a very limited way of doing it, and it doesn’t scale well.

Sparing the gory details, the general methods he used reduced 300 candidates to only 9 using a (relatively) simple calculation. And that’s not even considering many special cases. He’s working on finding similar patterns which might increase that reduction even further.

On those kinds of scales, it’s not that great. However, if by using the same technique, we can cull 95% of values out of a massive set of numbers (imagine a set of values where the size of the set itself is a number with thousands of digits), then that’s an immeasureable speed gain over calculating primes through brute force.

So I’m tasked with not only understanding these calculations, but writing an implementation of them in a computer program. Wish me luck.