• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# get_primes7 - Free Pascal version

a guest Jul 8th, 2012 115 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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;
RAW Paste Data
Top