Freepascal sieve

pascal_sieve.pas

program primes;

uses
  fgl, SysUtils;

type
  TIntegerList = specialize TFPGList<integer>;

  function SieveEratosphen(n: integer): TIntegerList;
  var
    Next, i, step: integer;
    numbers: array of boolean;
  begin
    Assert(n > 2, 'N should be greater than 2');
    Next := 2;
    SetLength(numbers, n);
    for i := 0 to High(numbers) do numbers[i] := True;
    while Next * Next <= n do
    begin
      if numbers[Next] then
      begin
        for i := 0 to n - Next do
        begin
          step := Next * Next + i * Next;
          if step < n then
            numbers[step] := False
          else
            break;
        end;
      end;
      Next += 1;
    end;

    Result := TIntegerList.Create;
    for i := 0 to n do
      if (i >= 2) and (numbers[i]) then Result.Add(i);
  end;

var
  Result: TIntegerList;
  start, elapsed: QWord;
begin
  start := getTickCount64;
  Result := SieveEratosphen(100000000);
  elapsed := getTickCount64 - start;
  writeln('Last prime is ' + IntToStr(Result.Last));
  writeln('Elapsed time is ' + IntToStr(elapsed) + ' ms');
  Result.Free;
end.