フォーラム


ゲスト  

ようこそ ゲスト さん。このフォーラムに投稿するには 登録が必要です。

ページ: [1]
トピック: 落ち着くためには素数を数えるといい
DEKO
管理者
投稿数: 2651
落ち着くためには素数を数えるといい
on: 2013/04/08 23:59 Mon

素数を求める関数を書いてみた…"エラトステネスのふるい" な、よくあるアルゴリズムのコード。

uses
..., Types;

// TIntegerDynArray = array of Integer;
// TBooleanDynArray = array of Boolean;

function PrimeNumber(const MaxValue: Integer): TIntegerDynArray;
var
Tbl: TBooleanDynArray;
i, j, Cnt: Integer;
begin
// 負数や 2 よりも小さい場合は抜ける
if MaxValue < 2 then
begin
SetLength(result, 0);
Exit;
end;

// 素数テーブルを初期化
SetLength(Tbl, MaxValue + 1);

// 2 を素数に設定、2 の倍数以外を対象に
Tbl[2] := True;
for i:=3 to High(Tbl) do
if Odd(i) then
Tbl[i] := True;

// 3 以降の素数を求める
for i:=3 to Trunc(Sqrt(MaxValue)) do
begin
if not Tbl[i] then
Continue;
for j:=2 to (MaxValue div i) do
Tbl[i*j] := False;
end;

// 素数の数を求め、戻り値の配列数を設定
Cnt := 0;
for i:=2 to High(Tbl) do
if Tbl[i] then
Inc(Cnt);
SetLength(result, Cnt);

// 戻り値として素数の動的配列を返す
Cnt := 0;
for i:=2 to High(Tbl) do
begin
if not Tbl[i] then
Continue;
result[Cnt] := i;
Inc(Cnt);
end;
end;

この関数は以下のようなコードで検証できる。フォームにボタンとメモを一つ貼って、ボタンの OnClick イベントハンドラを記述する。

procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;
PN: TIntegerDynArray;
begin
// 10 以下の素数: 4
// 100 以下の素数: 25
// 1000 以下の素数: 168
// 10000 以下の素数: 1229
// 100000 以下の素数: 9592
// 1000000 以下の素数: 78498
Memo1.Clear;
Memo1.Lines.BeginUpdate;
try
PN := PrimeNumber(StrToIntDef(Edit1.Text, 0));
Caption := Format('素数の数: %d', [Length(PN)]);
if Length(PN) > 0 then
begin
for i:=Low(PN) to High(PN) do
Memo1.Lines.Add(IntToStr(PN[i]));
end;
finally
Memo1.Lines.EndUpdate;
end;
end;
ページ: [1]
WP Forum Server by ForumPress | LucidCrew
バージョン: 1.7.5 ; ページロード: 0.022 sec.