Computers have made finding these large prime numbers possible. The faster computers can crunch numbers, the larger the primes will be found. Here's an interesting graph showing the largest known primes by year.

Simple Method of Finding Primes
A prime number is one that has no prime factors. So a simple way of checking if a number is prime is by trying all known primes less than it and seeing if it divides evenly into that number.

Example: Finding the first couple of primes

Starting off with the number 2, it is prime because the only divisors are itself and 1, meaning the only way to multiple two numbers to get 2 is 2 x 1. Likewise for 3.

So that starts us off with two known primes 2 and 3. To check the next number we can check if 4 modulo 2 equals 0. This means when divide 2 into 4 there is no remainder, which means 2 is a factor of 4. Specifically we know 2 x 2 = 4. Thus 4 is not prime.

Moving on to the next number: 5. To check five we try 5 modulo 2 and 5 modulo 3, both of which equals one. So 5 is prime, add it to our list of known primes and then continue on checking the next number. This rather tedious process is great for a computer.

This method can be a little slow when the number of primes gets large since you have to check every previous prime number. One way to speed this up is to stop checking when the prime squared is greater than the number.

For example if we are checking if 47 is prime, we can stop our check at 7, since 7 squared (49) is greater. If there were a larger factor that went into 47, it would have to be multiplied by a smaller prime number to give us 47, and we would have already found the smaller number earlier in our checks.

This method is called the Sieve of Eratosthenes (ca 240 BC), which is stated as:

Make a list of all the integers less than or equal to n (and greater than one). Strike out the multiples of all primes less than or equal to the square root of n, then the numbers that are left are the primes

The following python program will print out the primes from 2 to 1,000,000. On my Mac OS X PowerPC G4 500mhz it took approximately 4 minutes when printing to screen, and only 1 minute when output directed to a file.

If you don't have python, you can get it here for most platforms, or just review the code and rewrite in your preferred programming language.

Download Python Script: findthem.py

You can download this list of primes: primes_999983.zip (Zip 186kb)

After working on my Krypto problem I found that Python is really slow when compared to C. So I came back and wrote up a simple C version of this script.

Download C Program: findthem.c

In just 12 minutes, I was able to generate the 5,761,453 primes below 100 million, which is a 54mb text file!