[Back to MATH SWAG index]  [Back to Main SWAG index]  [Original]

{
GUY MCLOUGHLIN

>the way, it took about 20 mins. on my 386/40 to get prime numbers
>through 20000. I tried to come up With code to do the same With
>Turbo but it continues to elude me. Could anybody explain
>how to Write such a routine in Pascal?

  ...The following PRIME routine should prove to be a bit faster:
}

{ Find the square-root of a LongInt. }
Function FindSqrt(lo_IN : LongInt) : LongInt;

  { SUB : Find square-root For numbers less than 65536. }
  Function FS1(wo_IN : Word) : Word;
  Var
    wo_Temp1,
    wo_Temp2 : Word;
    lo_Error : Integer;
  begin
    if (wo_IN > 0) then
    begin
      wo_Temp1 := 1;
      wo_Temp2 := wo_IN;
      While ((wo_Temp1 shl 1) < wo_Temp2) do
      begin
        wo_Temp1 := wo_Temp1 shl 1;
        wo_Temp2 := wo_Temp2 shr 1;
      end;
      Repeat
        wo_Temp1 := (wo_Temp1 + wo_Temp2) div 2;
        wo_Temp2 := wo_IN div wo_Temp1;
        lo_Error := (LongInt(wo_Temp1) - wo_Temp2);
      Until (lo_Error <= 0);
      FS1 := wo_Temp1;
    end
    else
      FS1 := 0;
  end;

  { SUB : Find square-root For numbers greater than 65535. }
  Function FS2(lo_IN : longInt) : longInt;
  Var
    lo_Temp1,
    lo_Temp2,
    lo_Error : longInt;
  begin
    if (lo_IN > 0) then
    begin
      lo_Temp1 := 1;
      lo_Temp2 := lo_IN;
      While ((lo_Temp1 shl 1) < lo_Temp2) do
      begin
        lo_Temp1 := lo_Temp1 shl 1;
        lo_Temp2 := lo_Temp2 shr 1;
      end;

      Repeat
        lo_Temp1 := (lo_Temp1 + lo_Temp2) div 2;
        lo_Temp2 := lo_IN div lo_Temp1;
        lo_Error := (lo_Temp1 - lo_Temp2);
      Until (lo_Error <= 0);
      FS2 := lo_Temp1;
    end
    else
      FS2 := 0;
  end;

begin
  if (lo_IN < 65536) then
    FindSqrt := FS1(lo_IN)
  else
    FindSqrt := FS2(lo_IN);
end;

{ Check if a number is prime. }
Function Prime(lo_IN : LongInt) : Boolean;
Var
  lo_Sqrt,
  lo_Loop : LongInt;
begin
  if not odd(lo_IN) then
  begin
    Prime := (lo_IN = 2);
    Exit;
  end;
  if (lo_IN mod 3 = 0) then
  begin
    Prime := (lo_IN = 3);
    Exit;
  end;
  if (lo_IN mod 5 = 0) then
  begin
    Prime := (lo_IN = 5);
    Exit;
  end;

  lo_Sqrt := FindSqrt(lo_IN);
  lo_Loop := 7;
  While (lo_Loop < lo_Sqrt) do
  begin
    inc(lo_Loop, 2);
    if (lo_IN mod lo_Loop = 0) then
    begin
      Prime := False;
      Exit;
    end;
  end;
  Prime := True;
end;

[Back to MATH SWAG index]  [Back to Main SWAG index]  [Original]