home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / math.swg / 0029_Still More Primes.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-08-27  |  2.4 KB  |  112 lines
  1. {
  2. GUY MCLOUGHLIN
  3.  
  4. >the way, it took about 20 mins. on my 386/40 to get prime numbers
  5. >through 20000. I tried to come up With code to do the same With
  6. >Turbo but it continues to elude me. Could anybody explain
  7. >how to Write such a routine in Pascal?
  8.  
  9.   ...The following PRIME routine should prove to be a bit faster:
  10. }
  11.  
  12. { Find the square-root of a LongInt. }
  13. Function FindSqrt(lo_IN : LongInt) : LongInt;
  14.  
  15.   { SUB : Find square-root For numbers less than 65536. }
  16.   Function FS1(wo_IN : Word) : Word;
  17.   Var
  18.     wo_Temp1,
  19.     wo_Temp2 : Word;
  20.     lo_Error : Integer;
  21.   begin
  22.     if (wo_IN > 0) then
  23.     begin
  24.       wo_Temp1 := 1;
  25.       wo_Temp2 := wo_IN;
  26.       While ((wo_Temp1 shl 1) < wo_Temp2) do
  27.       begin
  28.         wo_Temp1 := wo_Temp1 shl 1;
  29.         wo_Temp2 := wo_Temp2 shr 1;
  30.       end;
  31.       Repeat
  32.         wo_Temp1 := (wo_Temp1 + wo_Temp2) div 2;
  33.         wo_Temp2 := wo_IN div wo_Temp1;
  34.         lo_Error := (LongInt(wo_Temp1) - wo_Temp2);
  35.       Until (lo_Error <= 0);
  36.       FS1 := wo_Temp1;
  37.     end
  38.     else
  39.       FS1 := 0;
  40.   end;
  41.  
  42.   { SUB : Find square-root For numbers greater than 65535. }
  43.   Function FS2(lo_IN : longInt) : longInt;
  44.   Var
  45.     lo_Temp1,
  46.     lo_Temp2,
  47.     lo_Error : longInt;
  48.   begin
  49.     if (lo_IN > 0) then
  50.     begin
  51.       lo_Temp1 := 1;
  52.       lo_Temp2 := lo_IN;
  53.       While ((lo_Temp1 shl 1) < lo_Temp2) do
  54.       begin
  55.         lo_Temp1 := lo_Temp1 shl 1;
  56.         lo_Temp2 := lo_Temp2 shr 1;
  57.       end;
  58.  
  59.       Repeat
  60.         lo_Temp1 := (lo_Temp1 + lo_Temp2) div 2;
  61.         lo_Temp2 := lo_IN div lo_Temp1;
  62.         lo_Error := (lo_Temp1 - lo_Temp2);
  63.       Until (lo_Error <= 0);
  64.       FS2 := lo_Temp1;
  65.     end
  66.     else
  67.       FS2 := 0;
  68.   end;
  69.  
  70. begin
  71.   if (lo_IN < 65536) then
  72.     FindSqrt := FS1(lo_IN)
  73.   else
  74.     FindSqrt := FS2(lo_IN);
  75. end;
  76.  
  77. { Check if a number is prime. }
  78. Function Prime(lo_IN : LongInt) : Boolean;
  79. Var
  80.   lo_Sqrt,
  81.   lo_Loop : LongInt;
  82. begin
  83.   if not odd(lo_IN) then
  84.   begin
  85.     Prime := (lo_IN = 2);
  86.     Exit;
  87.   end;
  88.   if (lo_IN mod 3 = 0) then
  89.   begin
  90.     Prime := (lo_IN = 3);
  91.     Exit;
  92.   end;
  93.   if (lo_IN mod 5 = 0) then
  94.   begin
  95.     Prime := (lo_IN = 5);
  96.     Exit;
  97.   end;
  98.  
  99.   lo_Sqrt := FindSqrt(lo_IN);
  100.   lo_Loop := 7;
  101.   While (lo_Loop < lo_Sqrt) do
  102.   begin
  103.     inc(lo_Loop, 2);
  104.     if (lo_IN mod lo_Loop = 0) then
  105.     begin
  106.       Prime := False;
  107.       Exit;
  108.     end;
  109.   end;
  110.   Prime := True;
  111. end;
  112.