Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

get_primes7 - Free Pascal version

By: a guest on Jul 8th, 2012  |  syntax: Pascal  |  size: 1.68 KB  |  hits: 55  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. type
  2.   IntArray = array of integer;
  3.  
  4. procedure generate(var Res: IntArray; Start: Integer; Cnt: Integer; Step: integer);
  5. var
  6.   Idx: integer;
  7.   CurrVal: Integer;
  8. begin
  9.   Idx := 0;
  10.   CurrVal := Start;
  11.   while (Idx < Cnt) do
  12.   begin
  13.      Res[Idx] := CurrVal;
  14.      Inc(CurrVal, Step);
  15.      Inc(Idx);
  16.   end;
  17. end;
  18.  
  19. procedure get_primes7(n: integer; var res: IntArray);
  20. var
  21.   cnt: integer;
  22.   s: IntArray;
  23.   mroot: Integer;
  24.   half: Integer;
  25.   i: Integer;
  26.   m: Integer;
  27.   j: Integer;
  28.   CurrLen, FoundCnt: Integer;
  29. begin
  30.   SetLength(res, 0);
  31.   if n < 2 then exit;
  32.  
  33.   if n = 2 then
  34.   begin
  35.     SetLength(res, 1);
  36.     res[0] := 2;
  37.     exit;
  38.   end;
  39.  
  40.   cnt := round((n - 3 + 2)/2);
  41.   SetLength(s, cnt);
  42.  
  43.   generate(s, 3, cnt, 2);
  44.  
  45.   mroot := round(sqrt(n));
  46.   half := Length(s);
  47.   i := 0;
  48.   m := 3;
  49.  
  50.   while (m <= mroot) do
  51.   begin
  52.     if s[i] > 0 then
  53.     begin
  54.       j := round((m * m - 3) / 2);
  55.       s[j] := 0;
  56.       while (j < half) do
  57.       begin
  58.         s[j] := 0;
  59.         Inc(j, m);
  60.       end;
  61.     end;
  62.  
  63.     Inc(i);
  64.     m := 2 * i + 3;
  65.   end;
  66.  
  67.  
  68.   CurrLen := 1;
  69.   FoundCnt := 1;
  70.   SetLength(res, CurrLen);
  71.   res[0] := 2;
  72.   for i := 0 to cnt - 1 do
  73.   begin
  74.     if s[i] > 0 then
  75.     begin
  76.       if FoundCnt = CurrLen then
  77.       begin
  78.         // Realokacja
  79.         CurrLen := round((CurrLen * 15) / 10);
  80.         SetLength(res, CurrLen);
  81.       end;
  82.       res[FoundCnt] := s[i];
  83.       Inc(FoundCnt);
  84.     end;
  85.   end;
  86.   SetLength(res, FoundCnt);
  87. end;
  88.  
  89. procedure RunTest;
  90. var
  91.   Res: IntArray;
  92.   i: Integer;
  93. begin
  94.   for i := 1 to 50 do
  95.   begin
  96.     get_primes7(1000000, res);
  97.     writeln('Found ', Length(res), ' prime numbers.');
  98.   end;
  99. end;
create a new version of this paste RAW Paste Data