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;

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 <= FMaxNumber do begin
        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 < 1) or (NumToCheck > FMaxNumber) then
    Raise Exception.Create('Invalid Prime Range ' + IntToStr(NumToCheck))
  else
    Result := not NotPrimeArray[NumToCheck];
end;

end.