🦒 🚣 🐰 ウィキペディアよりも速く数十億の単純な数字をふるいにかける 🧖🏽 😢 ✍🏿

（ 図のソース ）

エラトステネスのふるい（RE）は、コンピューターが発明されるずっと前に登場した最も古いアルゴリズムの1つであることはよく知られています。したがって、このアルゴリズムは何世紀にもわたって上下に研究されてきており、何も追加できないと考えるかもしれません。ウィキペディアを見ると、簡単にdrれることができる信頼できるソースへのリンクがたくさんあります。したがって、先日、Wikipediaで最適と表示されているオプションが大幅に最適化できることを偶然発見したとき、私は驚きました。

そんな感じでした。関数型プログラミング（FP）に関する記事の議論で、彼は質問をしました。このパラダイムでREを書く方法です。 FPの知識が乏しい以上、答えを判断する勇気はありませんが、議論の他の参加者はすぐに提案された解決策のいくつかを拒否し、理論的な複雑さの代わりに

O （ n l o g l o g n ）

$O（n \ log \ log n）$ （1）

提案された実装には計算の複雑さがあります

O （ n^{2} / l o g n ）

$O（n ^ 2 / \ log n）$ （2）

そして、そのような複雑さのために、たとえば1000万の数字がふるいにかけられるとき、あなたは待つことができません。私は興味を持ち、ウィキペディアに従って、通常の手続き型プログラミングを使用して最適なバージョンを実装しようとしました。 Delphi-7では、次のコードを取得しました。

リスト1

program EratosthenesSieve;
// Sieve of Eratosthenes
{$APPTYPE CONSOLE}

uses
  SysUtils, DateUtils,Math;
const
 version ='1.0.1d1';
 N = 1000000000; // number of primes
var
 sieve : array [2..N] of boolean; // false if prime
 t0, t1,dt : TDateTime;
 O,C : Extended;

procedure init;
  var
   i : integer;
  begin
   for i:=2 to n do
    sieve [i] := false;
  end; //init

procedure calc (start : integer);
  var
   prime, i : integer;
   breakLoop, exitProc : Boolean;
  begin
   prime := start;
   exitProc := false;
   repeat
// find next prime
      prime := prime+1;
      while (prime<N) and sieve[prime] do
       inc (prime);
      i:= sqr(prime);
// delete
      if i<= N then
        begin
          breakLoop := false;
          repeat
            if i<= N then
             begin
              sieve [i] := true;
              inc (i,prime);
             end
            else  // if i<= N
             breakLoop := true;
          until breakLoop;
        end  
      else // if prime+prime<= N
       exitProc := true;
   until exitProc;
  end; //calc

procedure print;
  var
    i :integer;
    found : integer;

  begin
    found := 0;
    for i:=2 to N do
     if not sieve [i] then
      begin
//       write (i,', ');
        inc(found);
      end;
    writeln;
    writeln ('Found ',found,' primes.');
  end; //

begin // program body
  writeln ('Sieve of Eratosthenes version ', version);
  writeln('N= ',N);

  init;
  t0 := now;
  writeln('Program started ',DateTimeToStr(t0));
  t0 := now;
  calc (1);
  t1 := now;
  writeln('Program finished ',DateTimeToStr(t1));
  dt := SecondSpan(t1,t0);
  writeln ('Time is ',FloatToStr(dt),' sec.');

  O := N* ln(ln(N));
  C := dt/O;
  writeln ('O(N ln ln N)= ',O,' C=',C);

  O := sqr(N)/ln(N);
  C := dt/O;
  writeln ('O(N*N/ln N)= ',O,' C=',C);

  print;
  
  writeln ('Press Enter to stop...');
  readln;
end.

sieve — , false, (not) . 3 : — init, ( ) — calc — print, . print: N=1000 .

calc : i

i^{2}, i^{2} + i, i^{2} + 2 i, \dots

$i^2, i^2+i, i^2+2i, …$

17.6 . (CPU Intel Core i7 3.4 ).

, .

1. 1) +=; 2) +=; 3) += .

1)

(2 n + 1) + (2 m + 1) = 2 n + 2 m + 2

$(2n+1)+(2m+1)=2n+2m+2$ 2. .

2)

(2 n + 1) + (2 m) = 2 n + 2 m + 1

$(2n+1)+(2m)=2n+2m+1$ 2 . .

3)

(2 n) + (2 m) = 2 n + 2 m

$(2n)+(2m)=2n+2m$ 2. .

2. .

.

(2 n + 1)^{2} = 4 n^{2} + 4 n + 1

$(2n+1)^{2}=4n^{2}+4n+1$ 2 . .

. , 2, .

:

i^{2}, i^{2} + 2 i, i^{2} + 4 i, \dots

$i^2, i^2+2i, i^2+4i, …$ (3)

. init.

program EratosthenesSieve;
// Sieve of Eratosthenes
{$APPTYPE CONSOLE}

uses
  SysUtils, DateUtils,Math;
const
 version ='1.0.1d1';
 N = 1000000000; // number of primes
var
 sieve : array [2..N] of boolean; // false if prime
 t0, t1,dt : TDateTime;
 O,C : Extended;

procedure init;
  var
   i : integer;
  begin
   for i:=2 to n do
    sieve [i] := not odd(i); 
  end; //init

procedure calc (start : integer);
  var
   prime,prime2, i : integer;
   breakLoop, exitProc : Boolean;
  begin
   prime := start;
   exitProc := false;
   repeat
// find next prime
      prime := prime+1;
      while (prime<N) and sieve[prime] do
       inc (prime);
//      i:= prime*prime;
      i:= sqr(prime);
      prime2 := prime+prime;   
// delete
      if i<= N then
        begin
          breakLoop := false;
          repeat
            if i<= N then
             begin
              sieve [i] := true;
              inc (i,prime2);
             end
            else  // if i<= N
             breakLoop := true;
          until breakLoop;
        end  
      else // if prime+prime<= N
       exitProc := true;
   until exitProc;
   sieve [2] := false;
  end; //calc

procedure print;
  var
    i :integer;
    found : integer;

  begin
    found := 0;
    for i:=2 to N do
     if not sieve [i] then
      begin
//      write (i,', ');
        inc(found);
      end;
    writeln;
    writeln ('Found ',found,' primes.');
  end; //

begin // program body
  writeln ('Sieve of Eratosthenes version ', version);
  writeln('N= ',N);

  init;
  t0 := now;
  writeln('Program started ',DateTimeToStr(t0));
  t0 := now;
  calc (2);
  t1 := now;
  writeln('Program finished ',DateTimeToStr(t1));
  dt := SecondSpan(t1,t0);
  writeln ('Time is ',FloatToStr(dt),' sec.');

  O := N* ln(ln(N));
  C := dt/O;
  writeln ('O(N ln ln N)= ',O,' C=',C);

  O := sqr(N)/ln(N);
  C := dt/O;
  writeln ('O(N*N/ln N)= ',O,' C=',C);

  print;
  
  writeln ('Press Enter to stop...');
  readln;
end.

9.9 . – .

,

d t = C * O,

$dt=C*O,$

d t

$dt$ – ;

C

$C$ – ;

O

$O$ – .

C

$C$ (1) (2).

N = 10^{6}

$N= 10^6$

d t

$dt$ .

N .

$N.$

$N$	(1)	(2)
$10^7$	$1.69\cdot 10^{-9}$	$2.74\cdot 10^{-9}$
$10^8$	$5.14 \cdot 10^{-9}$	$1.47 \cdot 10^{-8}$
$10^9$	$5.80 \cdot 10^{-9}$	$1.29 \cdot 10^{-7}$

, (1) . . , (3) , . , .

PS « » .

ウィキペディアよりも速く数十億の単純な数字をふるいにかける

More articles: