与えられた整数が素数かどうか判定する関数です。基本的には2から順に割
りきれるかどうか見ていくだけですが、高速化のために46349までの素数の表
をあらかじめ用意し、2から順に素数で割れるかどうかだけを見ていきます。

　32ビットintegerを前提にしています（Delphi 2.0 以降）。Cardinalや
Int64に対応させるにはかなり変更が必要です。

//以下がソース
unit Prime;

interface

{素数判定関数。素数なら真を返す}
function IsPrimeNumber(V : integer) : boolean;
{与えられた値以下の最大の素数を返す}
function NearPrimeNumber(const V : integer) : integer;

implementation

const
  SieveSize = 4793;
  (*---------------------------------------------------
     篩として用意する素数の表の要素数
     32ビットintegerの最大値は 2147483647
     この平方根までの大きさの素数が表の中身
     √2147483647=46340.9
     46340.9以下の最大の素数は46337
     46337は4792番目の素数
     従って、必要な篩のサイズは4792+1
  -----------------------------------------------------*)
var
  {素数のチェックのための篩（2..46349の素数表）}
  Sieve : array [1..SieveSize] of word;

{篩の生成(初期化時に実行)}
procedure MakeSieve;
var
  i, j,               (* ループカウンタ       *)
  Count : integer;    (* 素数の個数のカウンタ *)
begin
  Sieve[1] := 2;
  Count   := 1;
  i := 3;
  while Count < SieveSize do begin
    j := 1;
    while (Sqr(Sieve[j]) <= i) and (i mod Sieve[j] <> 0) do Inc(j);
    if Sqr(Sieve[j]) > i then begin
      Inc(Count);
      Sieve[Count] := i;
    end;
    Inc(i, 2);
  end;
end;

{素数判定関数。素数なら真を返す}
function IsPrimeNumber(V : integer) : boolean;
var
  i, Max : integer;
begin
  V := Abs(V);
  if V < 2 then begin
    Result := false;
    Exit;
  end;
  Result := True;
  i := 1;
  Max := Trunc(Sqrt(V));
  while Sieve[i] <= Max do begin
    if V mod Sieve[i] = 0 then begin
      Result := false;
      Exit;
    end else
      Inc(i);
  end;
end;

{与えられた値以下の最大の素数を返す}
function NearPrimeNumber(const V : integer) : integer;
begin
  if IsPrimeNumber(V) then Result := V
  else begin
    Result := V - 1;
    while true do begin
      if IsPrimeNumber(Result) then Exit;
      Dec(Result);
    end;
  end;
end;

initialization
  {篩を作っておく}
  MakeSieve;
end.


                              2001/05/20(Sun) 05:58pm  GFD03044 ひの
 


- FDELPHI  MES(16):玉石混淆みんなで作るSample蔵【見本蓄積】 01/05/28 -

Original document by ひの            氏 ID:(GFD03044)

ここにあるドキュメントは NIFTY SERVEの Delphi Users' Forum の16番会議室「玉石混淆みんなで作るSample蔵」に投稿されたサンプルです。これらのサンプルはボーランド株式会社がサポートする公式のものではありません。また、必ずしも動作が検証されているものではありません。これらのサンプルを使用したことに起因するいかなる損害も投稿者、およびフォーラムスタッフはその責めを負いません。使用者のリスクの範疇でご使用下さい。