Checking Prime Numbers

Now that we have a function for generating primes, the next library function we will need is to check whether a given number is prime.

The basic method for checking whether a given number n is prime is to use trial division. This involves dividing n by the prime integers from 2 to the square root of n. If any of these divisions result in an integer the number n is not prime, else it is prime. As we have already generated a list of primes we can refine this algorithm:

1. If n exists in our list it is prime, else proceed to step 2
2. If the maximum prime in our list is greater then or equal to n, than n is not prime, else proceed to step 3.
3. If the maximum prime in our list is greater then or equal to the square root of n, then proceed to step 5.
4. Clear the list, and then regenerate the list for all primes up to the square root of n.
5. Let p be the first prime in the list.
6. Divide n by p. If the result is an integer then n is not prime, else proceed to step 7.
7. If there are no more primes in the list then n is prime, else proceed to step 8.
8. Let p be the next prime in the list, then go to step 6.

This translates to this Delphi code:

function TfrmMain.IsPrime(index: int64): boolean;
var
maxPrime, rootPrime, p: int64;
i: integer;
begin
result := true;
if lstPrimes.IndexOf(Pointer(index)) <> -1 then exit;
result := false;
maxPrime := int64(lstPrimes.Items[lstPrimes.Count - 1]);
if maxPrime >= index then exit;
rootPrime := trunc(sqrt(index));
if maxPrime < rootPrime then GetPrimeList(rootPrime);
for i := 0 to lstPrimes.Count - 1 do begin
p := int64(lstPrimes.Items[i]);
if index mod p = 0 then exit;
end;
result := true;
end;

Now that we have these two procedures we are ready to attack the next problem in Project Euler.

Tags: ,