Generating Prime Numbers

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. Prime numbers appear in many of the problems in Project Euler, so I thought it would be a good idea to create some library functions to deal with these numbers. Today we are going to generate a list of prime numbers.

From Wikipedia:

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1. Create a list of consecutive integers from two to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
4. Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
5. Repeat steps 3 and 4 until p squared is greater than n.
6. All the remaining numbers in the list are prime.

Example

To find all the prime numbers less than or equal to 30, proceed as follows:

First generate a list of integers from 2 to 30:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Strike (sift out) the multiples of 2 resulting in:

2 3 5 7 9 11 13 15 17 19 21 23 25 27 29

The first number in the list after 2 is 3; strike the multiples of 3 from the list to get:

2 3 5 7 11 13 17 19 23 25 29

The first number in the list after 3 is 5; strike the remaining multiples of 5 from the list:

2 3 5 7 11 13 17 19 23 29

The first number in the list after 5 is 7, but 7 squared is 49 which is greater than 30 so the
process is finished. The final list consists of all the prime numbers less than or equal to 30.

This algorithm can be optimised by starting the crossing-off of multiples of each found prime number at the square of the number, as lower multiples have already been crossed out during the previous steps. Here is the Delphi implementation:

procedure TfrmMain.GetPrimeList(maxRange: integer);
var
  myArray: TBits;
  i, j: integer;
begin
  myArray := TBits.Create;
  try
    myArray.Size := maxRange + 1;
    lstPrimes.Clear;
    i := 2;
    while (i * i <= maxRange) do begin
      if not myArray[i] then begin
        j := i * i;
        while j <= maxRange do begin
          myArray[j] := true;
          inc(j, i);
        end;
      end;
      inc(i);
    end;
    for i := 2 to maxRange do
      if not myArray[i] then lstPrimes.Add(Pointer(i));
  finally
    myArray.Free;
  end;
end;

On my PC this code finds all the prime numbers in the range 2 to 10,000,000 in under a second.

Tags: ,

Comments are closed.