h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

I have always been fascinated by prime numbers. Particularly formulas and algorithms for generating them and determining whether or not x is prime.

For example, starting with 2 and feeding the result into the formula produces only Prime numbers. As far as I can tell. The trouble is that they grow VAST very quickly:

(2^x)-1

gives 3, 7, 127, ~1.7e38 and then what I *think* is the current largest known prime.

It is also interesting (although obvious when pointed out) that no prime number, when represented in any number base less than the value, will result in a number ending in a zero. That would mean it could be divided by the number base and therefore not be prime.
Take the prime number 7:
Base 2: 111
Base 3: 21
Base 4: 13
Base 5: 12
Base 6: 11

Knowing this it is easy to write a very fast computer program to list prime numbers, all without that tedious mucking about with divisions and modulos!

Have you written one then?

Naturally. If you can read "perl", try the following: (sorry about the indentation - my code is done "properly", honest!)

$TabWidth = 10;
$CurWidth = 0;
$MaxValue = 7500;
@PrimeValues = ();
@PrimeLog = ();
$PrimeLogSize = 0;
$StartValue = 2;

print "Prime numbers between $StartValue and $MaxValue.\n";
print "Calculated *without* the use of any kind of division or multiplication (just assignments and increments).\n";
for ($CurrentValue = $StartValue; $CurrentValue <= $MaxValue; ++$CurrentValue)
{
BumpLogValues();
if (IsPrime($CurrentValue))
{
print $CurrentValue." ";
if (++$CurWidth >= $TabWidth)
{
$CurWidth = 0;
}
AddPrime ($CurrentValue);
}
}
print "\n";

sub IsPrime
{
local ($TestValue) = (@_);
for ($PrimeCount = 1; $PrimeCount <= $PrimeLogSize; ++$PrimeCount)
{
if ($PrimeLog[$PrimeCount] == 0)
{
return (0);
}
}
return (1);
}

sub BumpLogValues
{
for ($PrimeCount = 1; $PrimeCount <= $PrimeLogSize; ++$PrimeCount)
{
if (++$PrimeLog[$PrimeCount] >= $PrimeValues[$PrimeCount])
{
$PrimeLog[$PrimeCount] = 0;
}
}
}

sub AddPrime
{
local ($NewPrime) = (@_);
$PrimeValues[++$PrimeLogSize] = $NewPrime;
$PrimeLog[$PrimeLogSize] = 0;
}