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

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;