How can I speed up a primality checker?

Question

I have a function FIsPrime which takes a int64 and returns a boolean True or False depending on whether the given int64 is prime or not.

function FIsPrime(P:int64):boolean;

  var
  I:int64;
  RSqrtP:Extended;

  begin
    I:= 3;
    RSqrtP := sqrt(P) + 1;

    while ((P mod I) <> 0) AND (I <= RSqrtP) AND ((P mod 2) <> 0) do
      I := I + 2;

    if I < RSqrtP then
      FIsPrime := False
    else
      FIsPrime := True;
  end;

However, while this works, it's quite slow. To check the numbers from 10⁶ to 5×10⁶ takes 4 seconds.

I'm testing numbers on the order of 10¹² and 10¹⁵ - the whole code picks a random number and × it by 10¹² to get a large random number.

This random number is run through the FIsPrime function and incremented by 1 untill it is prime:

function FFirstPrimeAbove(P:int64):int64;

  var
    BIsPrime: boolean;

  begin
    if P mod 2 = 0 then
      inc(P);

    repeat
      BIsPrime := FIsPrime(P);
      P := P + 2;
    until (BIsPrime);

    FFirstPrimeAbove := P;
  end;

This can take a while - around 6 seconds for 10¹² and 7 for 10¹⁵.

While 14 seconds isn't much, it is annoying. Is there a way to reduce this time with a more efficient algorithm?

I'm fairly new to Pascal, but have been programming for years - so any more efficient algorithm would be useful.

I looked at the AKS Test but there is a lot of jargon to overcome - "polynomial congruence relation", "generalization to polynomials" and "binomial coefficient" to pick a few.

Any basic hints as to how I could implement something in Delphi would be appreciated.

@AndreasRejbrand I'm writing it is Delphi - so an answer would be written in Delphi. Or do you mean the concept of a fast algorithm is unrelated? — Tim
Well in that case I suggest you do some research. Searching for prime testing algorithms will surely reveal something. — David Heffernan
@Tim. It depends on how often your are going to run this function. If you need it often storing intermediate primes up until the square root of your number may be wort it. For 10**14, you need to store the primes up until 10*7, of which there are approximately 5,761,455 (people.mpim-bonn.mpg.de/zagier/files/doi/10.1007/BF03039306/…) — Jan Doggen
Why did you call your function FIsPrime? What is the F for? Assign the bool like this: somebool := somecondition. — David Heffernan

Ken Bourassa Ken Bourassa · Accepted Answer · 2015-12-10T20:55:34

Changing RSqrtP to Int64 would most likely improve preformance. I didn't test it, but I'd expect comparing a float value to an int64 value not to be the fastest.

Take ((P mod 2) <> 0) out of the loop.

Also, if you don't mind having a longer initialisation time for your application, you could load a list of all prime between 2 and X and start with them before going to the I+2 routine. You don't need to try to divide by non prime number, as this is already taken care of by prime one (i.e. Anything that can be divided by 4 will be divided by 2, anything that can be divided by 49 will also be by 7, etc)

I posted an article about optimisation using primes as an example a while ago. Maybe you'll see some more information there that could help you.

How can I speed up a primality checker?

2 Answers