Mega Code Archive
Prime numbers
<![CDATA[
Title: Prime numbers
Question: Finding out if a given number is prime
Answer:
There are some ways of finding if given number (N) is prime.
Start a loop from 2 to Sqrt(N) and if it divides with no remainder then it is not prime. Here is a source code to a simple function:
function IsPrime(N: Integer): Boolean;
var
A: Integer;
begin
for A := 2 to Trunc(Sqrt(N)) do
if (N mod A) = 0 then
begin
Result := False;
Exit;
end;
Result := True;
end;
We can see that the larger the value of N is, the longer it takes to determine if it is prime number. But what if we have to find all the prime numbers from 1 to one million, or even more? This function will be fast for the first checks but will become slower later.
Fortunately there is better solution and it is called Eratostene sieve. The idea is simple: we have a Boolean. We start with the number 2 and mark every second element as not prime (it can be divided by 2). Then continue with 3 (all that can be divided by 3 became False) and so on. And in the end (it doesent even matter just joking, Hi guys from Linkin Park :) we have an array with True values indicating which number is prime.
Here is source code of the procedure I have written:
var
NotPrime: array of Boolean;
procedure GeneratePrimes(MaxNum: Integer);
var
A, B: Integer;
begin
SetLength(NotPrime, MaxNum - 1); // we don't need to check the 1
for A := 2 to MaxNum div 2 do
if not NotPrime[A - 2] then
begin
B := A + A; // start from the second element
while B begin
NotPrime[B - 2] := True;
Inc(B, A);
end;
end;
end;
Ive used NotPrime and not IsPrime for name, and I use False to indicate it is prime, so I can benefit from the fact that a global array is already initialized with False values.
See the attached file to see an application written with this function.
GeneratePrimes is actually pretty fast. Its speed depends on the amout of RAM you have on your PC. It can find the first 100 million primes for about 3 secs!!!
There are some improvements that can be made to these functions to make them faster. I wanted to demonstrate the algorithm itself and not to do the faster algorithm possible.
]]>