Finding Prime Numbers

A programming project and case study

Ben Rehberg
February 26, 2006

I remember reading some time ago about Google's infamous billboard somewhere in the U.S. that simply said "{first 10-digit prime in consecutive numbers of e}.com." Just a few days ago I read the article in Time magazine about Google and it mentioned the billboard again. They gave the answer (7427466391.com) and it led me to this small project, since I've been hunting for a programming project lately. I'm not out to prove anything that hasn't been proven yet, but I am conducting my own small study so that I may learn and share this knowledge. All the code I'm writing is in PERL.

Google helped me find some good information. Fun with Prime Numbers by Steve Litt helped to put this tiny project into perspective, providing the complete source of his program in C. His article is where I drew most of the algorithm, but I wrote the code here myself in PERL. I also found Prime Numbers by Marcus Kazmierczak. He provides a Python implementation as well as another C program, but it is not as well documented.

About the Systems I'm Using

I don't know how to calculate probabilities for run-times for any system, but I can tell you a bit about what I'm running these scripts on, so you may have some idea about how long to expect it to take.

The first system is very old. It is a Compaq Presario 5155 equipped with an AMD K6-2 running at 350MHz. It has 128MB RAM and runs Fedora Core 4 with the latest kernel. I use this system primarily for automated tasks, such as checking whether my ISP's mail server is blacklisted by SpamCop.

The second system, which happens to be the newest machine in the place, is a Hewlett-Packard TC1100 Tablet PC. It has an Intel Centrino running at approximately 1GHz and 1GB RAM and operates (obviously) on Windows XP Tablet PC edition. I use this primarily for work as I travel quite a bit.

The following is a copy of the first script run to find primes between 5 and 99,999,999. Forgive me for the display of the code as this page is completely hand-coded. You can find the file here.


#! /usr/bin/perl -w



#I'm going to try to find prime numbers up to whatever STOP is.



$stop=99999999;

$start=5;

$candidate=2;

$divisor=0;

$prime=0;

$numprimes=0;



$begin=time;

for ($candidate=$start; $candidate <= $stop; $candidate++){

	$divisor=2;

$prime=1;

while (($divisor * $divisor) <= $candidate){

	if ($candidate % $divisor == 0)

		{

			$prime=0;

			last;

		}

	$divisor++;

	}

	if($prime) {print "$candidate \n"; $numprimes++;}

	}

$end=time;

$elapsed=$end-$begin;

print "Between $start and $stop I found $numprimes prime numbers.\n";

print "This took $elapsed seconds.\n";

Explanation of What the Code Does

I'm not going to go line-by-line; I hate when people do that. I'll give a narrative of the source code:

First I initialize some variables. start and stop define the range of values I'll look in to find primes. The candidate is the current value we're analyzing to see if it's prime. The divisor is the determinant of the prime number, and we start that at two. I'm using the prime variable as a boolean value to flag a number as "prime" or "not prime." The program will simply print the number to standard output if it is a prime. This is only for time; we don't need to keep them.

My loop does modulo division of the candidate by the divisor. This starts a process of elimination of each candidate, as each candidate is tested for even division by numbers from two up to the candidate's square root (or as close as an integer can get to it). At this point the divisor squared would approximate the candidate, and all the possible two products needed to produce the candidate number have been tried. If modulo division is never zero, the number must be prime. This is about the simplest way to find prime numbers, but is very inefficient. It is very slow, and I think the number one reason it's slow is that it actually uses all numbers for candidates, including even numbers.

Even numbers are divisible by two. Half the integers on the number line are even. There are no even prime numbers except the number two. That rules everything else out. So the next bit of code is modified so that the candidate number is only an odd number. This should reduce processing time dramatically.