The purpose of this tutorial is to demonstrate how an algorithm is first formed as a solution to a problem, and also how we can make the algorithm more efficient in terms of speed. The problem we will be looking at is how to check which numbers are prime numbers within the range of 1 to 10,000,000.

First of all what is a prime number? A mathematician would say a prime is “a number which is only divisible by two numbers, 1 and itself”. You should note at this point that 1 is not a prime number because it is only divisible by one number, 1. So now we know what a prime is how are we going to test for one? With complex problems the simplest solutions are often the most effective, we will adopt this philosophy and code the simplest solution and then build upon this.

The simplest solution would be to increment a variable X from 1 to 10,000,000 and have a nested loop within this incrementing a variable Y from 1 to X and trying to divide X by Y. We also need an initial check in there to see if the number is less than 2, which would not be a prime. You should get something like this in Delphi code which at this stage I suggest you do not run:

Simple Solution
function PrimeCycle: string;
var
  X:  Integer;
begin
  Result := '';
  X := 1;
  while X <= 10000000 do
  begin
    if BasicIsPrime(X) then
      Result := Result + IntToStr(X) + ', ';
    Inc(X);
  end;
end;
 
function BasicIsPrime(Number: Integer): Boolean;
var
  Y: Integer;
begin
  if Number <= 1 then
    Result := False
  else
  begin
    Y := 2;
    Result := True;
    while Y < Number do
    begin
      if Number mod Y = 0 then
      begin
        Result := False;
        Break;
      end;
      Inc(Y);
    end;
  end;
end; 
   

Now let’s discuss the efficiency of this solution. Being the simplest solution to the problem it has a major flaw, although the ‘BasicIsPrime’ function works and produces no false positives or negatives it takes at least three hours on a fast modern PC to complete. So we need to do something about this and the best place to start is to go back to the drawing board and look at the how we are identifying a prime number.

So what we are doing is iterating through 2 until X – 1 to establish if any value of Y is a factor of X. If we look at this logically there is no need to iterate up until X – 1. If we look at X = 100, and therefore define the range as 2 to 99 then we only actually need to iterate through until X/2, i.e. 2 to 50. This is simply because if we are dividing X by 50 we are also dividing it by 100 as 100 is a multiple of 50, and so on; therefore the range 2 to X/2 actually covers all of the range 2 to X – 1.

What we have done so far is halved the range we need to check, and we can time this using the GetTickCount function:

Simple Solution - Version2
function PrimeCycle(var Speed: Double): string;
var
  X:      Integer;
  Start,
  Finish: Cardinal;
begin
  Result := '';
  X := 1;
  Start := GetTickCount;
  while X <= 10000000 do
  begin
    if BasicIsPrime(X) then
      Result := Result + IntToStr(X) + ', ';
    Inc(X);
  end;
  Finish := GetTickCount;
  Speed := (Finish - Start) / 1000;
end;
 
function BasicIsPrime(Number: Integer): Boolean;
var
  Y: Integer;
begin
  if Number <= 1 then
    Result := False
  else
  begin
    Y := 2;
    Result := True;
    while Y <= (Number div 2) do
    begin
      if Number mod Y = 0 then
      begin
        Result := False;
        Break;
      end;
      Inc(Y);
    end;
  end;
end; 
   

For example 2 we are actually doing 12,500,002,500,000, which is roughly 3.9 times less. So we have gone from around three hours right down to around forty-six minutes just by simplifying the problem, and we’re not finished there.

For any of you that know about square roots may have already spotted this. Instead of checking the range X/2 in the ‘BasicIsPrime’ function we only need to check up until the square root of X. This is purely because by nature the square root of X is the smallest factor of X which also covers the full range up until X. This further optimisation will reduce or completion time down to a more bearable eighteen minutes, and we haven’t even looked at optimising the actual code itself, only the mathematical algorithm.

Before we look at the actual Delphi code optimisations there is one blindingly obvious issue sticking out like a sore thumb. Why are we checking even numbers after two when none of them can possible be a prime? In fact why are we checking multiples or 2, 3, 5, and 7 once they are gone? To eliminate these issues you should have something like this example and also an algorithm which find all prime numbers from 1 to 10,000,000 in less than a minute (depending on your CPU speed):

Simple Solution - Version3
function BasicIsPrime(Number: Integer): Boolean;
var
  Y: Integer;
begin
  if Number <= 1 then
    Result := False
  else if Number <= 3 then
    Result := True
  else if Number = 5 then
    Result := True
  else if Number = 7 then
    Result := True
  else if Number mod 2 = 0 then
    Result := False
  else if Number mod 3 = 0 then
    Result := False
  else if Number mod 5 = 0 then
    Result := False
  else if Number mod 7 = 0 then
    Result := False
  else
  begin
    Y := 7;
    Result := True;
    while Y <= Round(Sqrt(Number)) do
    begin
      if Number mod Y = 0 then
      begin
        Result := False;
        Break;
      end;
      Inc(Y, 2);
    end;
  end;
end; 
   

First let’s look at our while loop in our ‘BasicIsPrime’ function and consider the question, is the rounded square root of Number ever going to change in each instance of ‘BasicIsPrime’? The answer is clearly no, however on each iteration of the while loop we are calculating its value again and adding to the completion time unnecessarily. By assigning the rounded square root of Number to a variable before starting the loop we only calculate the value once and therefore shave valuable wasted time off the completion time.

Efficient logic
    ...
    Sqr := Round(Sqrt(Number));
    while Y <= Sqr do
    ... 
   

Summary

Hopefully now you will have a good understanding of how to implement mathematical solutions involving algorithms by simplifying the math, logic and code to reduce the number of CPU clock cycles required till completion. From this introductory tutorial you should also be able the optimise the 'PrimeCycle' function by implementing some of the techniques demonstrated here and thus further reduce completion time significantly. There are yet more efficient ways to solve this problem for you to investigate on your own which involve number sieves and other mathematical techniques, as well as other programming techniques such as inline ASM.