Mega Code Archive
Prime Number Class (Fast Access to Prime Numbers)
<![CDATA[
Title: Prime Number Class (Fast Access to Prime Numbers)
Question: In a recent article by Upportune Malters (ID 2989) he presents an algorythm that populates a boolean array that denotes if a number is prime or not. This is an efficient idea in that once the array is generated then checking of a prime numbers is a simple check to the array element.
This prompted me to write a Class that uses Borland's TBit class. The TBit class is more memory efficient than an array of boolean in that 8 true/false values can be stored in a byte, whereas the boolean array can only store 1 true/false value in a byte.
Using the class one can check if a number is prime, obtain a list of all prime numbers from x to y.
eg.
var PN : TPrimeNumbers;
formshow or create
PN := TPrimeNumbers.Create(1000000); // Specify max number
end;
some routine
if PN.IsPrime(2341) then ...
for i := 1 to 1000 do if PN.IsPrime(i) then
ListBox1.Add(IntToStr(i));
etc...
end;
closeform
PN.Free;
end;
Answer:
interface
type
TPrimeNumbers = class(TObject)
private
NotPrimeArray : TBits; // Borland Bit array class
FMaxNumber : integer;
public
constructor Create(MaxNumber : integer);
destructor Destroy; override;
function IsPrime(NumToCheck : integer) : boolean;
end;
// -----------------------------------------------------------------------------
interface
constructor TPrimeNumbers.Create(MaxNumber : integer);
var A,B : integer;
begin
NotPrimeArray := TBits.Create; // False = PRIME
NotPrimeArray.Size := MaxNumber + 1;
FMaxNumber := MaxNumber;
for A := 2 to FMaxNumber div 2 do
if not NotPrimeArray[A] then begin
B := A + A; // Start from 2nd element
while B NotPrimeArray[B] := true; // Set NOT PRIME
inc(B,A);
end;
end;
NotPrimeArray[1] := true; // Set elements 1 and 2
NotPrimeArray[2] := false;
end;
destructor TPrimeNumbers.Destroy;
begin
NotPrimeArray.Free;
end;
function TPrimeNumbers.IsPrime(NumToCheck : integer) : boolean;
begin
if (NumToCheck FMaxNumber) then
Raise Exception.Create('Invalid Prime Range ' + IntToStr(NumToCheck))
else
Result := not NotPrimeArray[NumToCheck];
end;
end.
]]>