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:

- If n exists in our list it is prime, else proceed to step 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.
- If the maximum prime in our list is greater then or equal to the square root of n, then proceed to step 5.
- Clear the list, and then regenerate the list for all primes up to the square root of n.
- Let p be the first prime in the list.
- Divide n by p. If the result is an integer then n is not prime, else proceed to step 7.
- If there are no more primes in the list then n is prime, else proceed to step 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: Mathematics, Project Euler