procedure pchisla(n:longint; var b:array of longint);
var i,j,x:longint;
    boo,shag:boolean;
begin
  if n>1 then
  b[0]:=1;
  if n>2 then
  b[1]:=2;
  if n>3 then
  b[2]:=3;
  if n>5 then
  b[3]:=5;
  boo:=true;
  x:=4;
  i:=7;
  shag:=true;
  repeat
    j:=2;
    repeat
      if (i mod b[j]=0) then
      boo:=false;
      j:=j+1;
    until b[j]>(trunc(sqrt(i))+1);
    if boo then
    begin
      b[x]:=i;
      writeln(i,' ');
      x:=x+1;
    end;
    boo:=true;
    if shag then
      i:=i+4
    else
      i:=i+2;
    shag:=not(shag);
  until i>=n;
end;

procedure pchisla(n:longint; var b:array of longint);
var i,j,x:longint;
    boo,shag:boolean;
begin
  if n>1 then
  b[0]:=1;
  if n>2 then
  b[1]:=2;
  if n>3 then
  b[2]:=3;
  if n>5 then
  b[3]:=5;
  boo:=true;
  x:=4;
  i:=7;
  shag:=true;
  repeat
    for j:=5 to (trunc(sqrt(i))+1) do
      if (i mod j=0) then
      boo:=false;
      if boo then
      begin
        b[x]:=i;
        x:=x+1;
      end;
      boo:=true;
      if shag then
        i:=i+4
      else
        i:=i+2;
      shag:=not(shag);
  until i>=n;
end;

procedure pchisla(n:longint; var b:array of longint);
var
ide,jde,c1de,xide:longint;
kde:boolean;
begin
  b[0]:=2;
  b[1]:=3;
  kde:=true;
  xide:=2;
  ide:=4;
  repeat
  for jde:=2 to (trunc(sqrt(ide))+1) do if (ide mod jde=0) then kde:=false;
    if kde then
      begin
      b[xide]:=ide;
      xide:=xide+1;
      end;
    kde:=true;
    ide:=ide+1;
  until (xide=n);
end;

begin
  WriteLn(1)
end.

var
  Simple: array of Integer;
  i, j, n: Integer;
  tmp: Real;
  chk: Boolean;

begin
  Writeln('Enter Digit');  ReadLn(n);
  i := 0;
  if n >= 1 then
  begin
    i := 2;
    SetLength(Simple, 1);
    Simple[0] := 1;
  end;
  while i <= n do
  begin
    if i < 3 then
    begin
      SetLength(Simple, Length(Simple) + 1);
      Simple[Length(Simple) - 1] := i;
      Inc(i);
    end
    else
    begin
      j := 1; chk := True;
      tmp := Sqrt(i);
      if (tmp - Round(tmp)) <> 0 then
      begin
      repeat
          if (i mod Simple[j] = 0) then
            chk := False;
          Inc(j);
        until (not chk) or
              (Simple[j] > tmp) or
              (j = Length(Simple));
      end
      else
        chk := False;
      if chk then
      begin
        SetLength(Simple, Length(Simple) + 1);
        Simple[Length(Simple) - 1] := i;
      end;
      Inc(i, 2);
    end;
  end;
  Writeln;
  for i := 0 to Length(Simple) - 1 do
    write(IntToStr(Simple[i]) + ' ');
  Writeln;
  Readln;
end.

unit Atkin;
// Решето Аткина
// А.О.Л. Аткин (A.O.L. Atkin), Дэниел Бернштайн (Daniel J. Bernstein)
// http://cr.yp.to/papers/primesieves-19990826.pdf

interface

const
  PRIMEGEN_WORDS = 2048;
  const B32 = PRIMEGEN_WORDS;
  const B = (PRIMEGEN_WORDS * 32);

type
  TLongArray = array[0..PRIMEGEN_WORDS*16-1] of LongWord;
  PLongArray = ^TLongArray;

  TPrimeType = integer;

  TAtkinSieve = class(TObject)
  private
    buf: array [0..16-1, 0..PRIMEGEN_WORDS-1] of LongWord;
    p: array [0..512-1] of TPrimeType; // p[num-1] ... p[0], in that order
    num: integer;
    pos: integer; // next entry to use in buf; WORDS to restart
    Fbase: TPrimeType;
    L: TPrimeType;
    procedure Init;
    procedure Generate;
    procedure Clear;
    procedure Fill;
  protected
    function GetCurrent: TPrimeType;
  public
    constructor Create;
    function Next: TPrimeType;
    procedure SkipTo(v: TPrimeType);
  end;

implementation

type
  TTodo = record
    index, f, g, k: ShortInt;
  end;

  TArray49 = array[0..48] of Cardinal;

const
  two: array[0..31] of LongWord = (
    $00000001, $00000002, $00000004, $00000008,
    $00000010, $00000020, $00000040, $00000080,
    $00000100, $00000200, $00000400, $00000800,
    $00001000, $00002000, $00004000, $00008000,
    $00010000, $00020000, $00040000, $00080000,
    $00100000, $00200000, $00400000, $00800000,
    $01000000, $02000000, $04000000, $08000000,
    $10000000, $20000000, $40000000, $80000000
  );

  deltainverse: array[0..59] of integer = (
    -1, B32*0, -1, -1, -1, -1, -1, B32*1, -1, -1, -1, B32*2, -1, B32*3, -1,
    -1, -1, B32*4, -1, B32*5, -1, -1, -1, B32*6, -1, -1, -1, -1, -1, B32*7,
    -1, B32*8, -1, -1, -1, -1, -1, B32*9, -1, -1, -1, B32*10, -1, B32*11, -1,
    -1, -1, B32*12, -1, B32*13, -1, -1, -1, B32*14, -1, -1, -1, -1, -1, B32*15
  );

  for4: array [0..127] of TTodo = (
    (index: 0; f: 2; g: 15; k: 4),
    (index: 0; f: 3; g: 5; k: 1),
    (index: 0; f: 3; g: 25; k: 11),
    (index: 0; f: 5; g: 9; k: 3),
    (index: 0; f: 5; g: 21; k: 9),
    (index: 0; f: 7; g: 15; k: 7),
    (index: 0; f: 8; g: 15; k: 8),
    (index: 0; f: 10; g: 9; k: 8),
    (index: 0; f: 10; g: 21; k: 14),
    (index: 0; f: 12; g: 5; k: 10),
    (index: 0; f: 12; g: 25; k: 20),
    (index: 0; f: 13; g: 15; k: 15),
    (index: 0; f: 15; g: 1; k: 15),
    (index: 0; f: 15; g: 11; k: 17),
    (index: 0; f: 15; g: 19; k: 21),
    (index: 0; f: 15; g: 29; k: 29),
    (index: 3; f: 1; g: 3; k: 0),
    (index: 3; f: 1; g: 27; k: 12),
    (index: 3; f: 4; g: 3; k: 1),
    (index: 3; f: 4; g: 27; k: 13),
    (index: 3; f: 6; g: 7; k: 3),
    (index: 3; f: 6; g: 13; k: 5),
    (index: 3; f: 6; g: 17; k: 7),
    (index: 3; f: 6; g: 23; k: 11),
    (index: 3; f: 9; g: 7; k: 6),
    (index: 3; f: 9; g: 13; k: 8),
    (index: 3; f: 9; g: 17; k: 10),
    (index: 3; f: 9; g: 23; k: 14),
    (index: 3; f: 11; g: 3; k: 8),
    (index: 3; f: 11; g: 27; k: 20),
    (index: 3; f: 14; g: 3; k: 13),
    (index: 3; f: 14; g: 27; k: 25),
    (index: 4; f: 2; g: 1; k: 0),
    (index: 4; f: 2; g: 11; k: 2),
    (index: 4; f: 2; g: 19; k: 6),
    (index: 4; f: 2; g: 29; k: 14),
    (index: 4; f: 7; g: 1; k: 3),
    (index: 4; f: 7; g: 11; k: 5),
    (index: 4; f: 7; g: 19; k: 9),
    (index: 4; f: 7; g: 29; k: 17),
    (index: 4; f: 8; g: 1; k: 4),
    (index: 4; f: 8; g: 11; k: 6),
    (index: 4; f: 8; g: 19; k: 10),
    (index: 4; f: 8; g: 29; k: 18),
    (index: 4; f: 13; g: 1; k: 11),
    (index: 4; f: 13; g: 11; k: 13),
    (index: 4; f: 13; g: 19; k: 17),
    (index: 4; f: 13; g: 29; k: 25),
    (index: 7; f: 1; g: 5; k: 0),
    (index: 7; f: 1; g: 25; k: 10),
    (index: 7; f: 4; g: 5; k: 1),
    (index: 7; f: 4; g: 25; k: 11),
    (index: 7; f: 5; g: 7; k: 2),
    (index: 7; f: 5; g: 13; k: 4),
    (index: 7; f: 5; g: 17; k: 6),
    (index: 7; f: 5; g: 23; k: 10),
    (index: 7; f: 10; g: 7; k: 7),
    (index: 7; f: 10; g: 13; k: 9),
    (index: 7; f: 10; g: 17; k: 11),
    (index: 7; f: 10; g: 23; k: 15),
    (index: 7; f: 11; g: 5; k: 8),
    (index: 7; f: 11; g: 25; k: 18),
    (index: 7; f: 14; g: 5; k: 13),
    (index: 7; f: 14; g: 25; k: 23),
    (index: 9; f: 2; g: 9; k: 1),
    (index: 9; f: 2; g: 21; k: 7),
    (index: 9; f: 3; g: 1; k: 0),
    (index: 9; f: 3; g: 11; k: 2),
    (index: 9; f: 3; g: 19; k: 6),
    (index: 9; f: 3; g: 29; k: 14),
    (index: 9; f: 7; g: 9; k: 4),
    (index: 9; f: 7; g: 21; k: 10),
    (index: 9; f: 8; g: 9; k: 5),
    (index: 9; f: 8; g: 21; k: 11),
    (index: 9; f: 12; g: 1; k: 9),
    (index: 9; f: 12; g: 11; k: 11),
    (index: 9; f: 12; g: 19; k: 15),
    (index: 9; f: 12; g: 29; k: 23),
    (index: 9; f: 13; g: 9; k: 12),
    (index: 9; f: 13; g: 21; k: 18),
    (index: 10; f: 2; g: 5; k: 0),
    (index: 10; f: 2; g: 25; k: 10),
    (index: 10; f: 5; g: 1; k: 1),
    (index: 10; f: 5; g: 11; k: 3),
    (index: 10; f: 5; g: 19; k: 7),
    (index: 10; f: 5; g: 29; k: 15),
    (index: 10; f: 7; g: 5; k: 3),
    (index: 10; f: 7; g: 25; k: 13),
    (index: 10; f: 8; g: 5; k: 4),
    (index: 10; f: 8; g: 25; k: 14),
    (index: 10; f: 10; g: 1; k: 6),
    (index: 10; f: 10; g: 11; k: 8),
    (index: 10; f: 10; g: 19; k: 12),
    (index: 10; f: 10; g: 29; k: 20),
    (index: 10; f: 13; g: 5; k: 11),
    (index: 10; f: 13; g: 25; k: 21),
    (index: 13; f: 1; g: 15; k: 3),
    (index: 13; f: 4; g: 15; k: 4),
    (index: 13; f: 5; g: 3; k: 1),
    (index: 13; f: 5; g: 27; k: 13),
    (index: 13; f: 6; g: 5; k: 2),
    (index: 13; f: 6; g: 25; k: 12),
    (index: 13; f: 9; g: 5; k: 5),
    (index: 13; f: 9; g: 25; k: 15),
    (index: 13; f: 10; g: 3; k: 6),
    (index: 13; f: 10; g: 27; k: 18),
    (index: 13; f: 11; g: 15; k: 11),
    (index: 13; f: 14; g: 15; k: 16),
    (index: 13; f: 15; g: 7; k: 15),
    (index: 13; f: 15; g: 13; k: 17),
    (index: 13; f: 15; g: 17; k: 19),
    (index: 13; f: 15; g: 23; k: 23),
    (index: 14; f: 1; g: 7; k: 0),
    (index: 14; f: 1; g: 13; k: 2),
    (index: 14; f: 1; g: 17; k: 4),
    (index: 14; f: 1; g: 23; k: 8),
    (index: 14; f: 4; g: 7; k: 1),
    (index: 14; f: 4; g: 13; k: 3),
    (index: 14; f: 4; g: 17; k: 5),
    (index: 14; f: 4; g: 23; k: 9),
    (index: 14; f: 11; g: 7; k: 8),
    (index: 14; f: 11; g: 13; k: 10),
    (index: 14; f: 11; g: 17; k: 12),
    (index: 14; f: 11; g: 23; k: 16),
    (index: 14; f: 14; g: 7; k: 13),
    (index: 14; f: 14; g: 13; k: 15),
    (index: 14; f: 14; g: 17; k: 17),
    (index: 14; f: 14; g: 23; k: 21)
  );

  for6: array[0..47] of TTodo = (
    (index: 1; f: 1; g: 2; k: 0),
    (index: 1; f: 1; g: 8; k: 1),
    (index: 1; f: 1; g: 22; k: 8),
    (index: 1; f: 1; g: 28; k: 13),
    (index: 1; f: 3; g: 10; k: 2),
    (index: 1; f: 3; g: 20; k: 7),
    (index: 1; f: 7; g: 10; k: 4),
    (index: 1; f: 7; g: 20; k: 9),
    (index: 1; f: 9; g: 2; k: 4),
    (index: 1; f: 9; g: 8; k: 5),
    (index: 1; f: 9; g: 22; k: 12),
    (index: 1; f: 9; g: 28; k: 17),
    (index: 5; f: 1; g: 4; k: 0),
    (index: 5; f: 1; g: 14; k: 3),
    (index: 5; f: 1; g: 16; k: 4),
    (index: 5; f: 1; g: 26; k: 11),
    (index: 5; f: 5; g: 2; k: 1),
    (index: 5; f: 5; g: 8; k: 2),
    (index: 5; f: 5; g: 22; k: 9),
    (index: 5; f: 5; g: 28; k: 14),
    (index: 5; f: 9; g: 4; k: 4),
    (index: 5; f: 9; g: 14; k: 7),
    (index: 5; f: 9; g: 16; k: 8),
    (index: 5; f: 9; g: 26; k: 15),
    (index: 8; f: 3; g: 2; k: 0),
    (index: 8; f: 3; g: 8; k: 1),
    (index: 8; f: 3; g: 22; k: 8),
    (index: 8; f: 3; g: 28; k: 13),
    (index: 8; f: 5; g: 4; k: 1),
    (index: 8; f: 5; g: 14; k: 4),
    (index: 8; f: 5; g: 16; k: 5),
    (index: 8; f: 5; g: 26; k: 12),
    (index: 8; f: 7; g: 2; k: 2),
    (index: 8; f: 7; g: 8; k: 3),
    (index: 8; f: 7; g: 22; k: 10),
    (index: 8; f: 7; g: 28; k: 15),
    (index: 11; f: 1; g: 10; k: 1),
    (index: 11; f: 1; g: 20; k: 6),
    (index: 11; f: 3; g: 4; k: 0),
    (index: 11; f: 3; g: 14; k: 3),
    (index: 11; f: 3; g: 16; k: 4),
    (index: 11; f: 3; g: 26; k: 11),
    (index: 11; f: 7; g: 4; k: 2),
    (index: 11; f: 7; g: 14; k: 5),
    (index: 11; f: 7; g: 16; k: 6),
    (index: 11; f: 7; g: 26; k: 13),
    (index: 11; f: 9; g: 10; k: 5),
    (index: 11; f: 9; g: 20; k: 10)
  );

  for12: array[0..95] of TTodo = (
    (index: 2; f: 2; g: 1; k: 0),
    (index: 2; f: 2; g: 11; k: -2),
    (index: 2; f: 2; g: 19; k: -6),
    (index: 2; f: 2; g: 29; k: -14),
    (index: 2; f: 3; g: 4; k: 0),
    (index: 2; f: 3; g: 14; k: -3),
    (index: 2; f: 3; g: 16; k: -4),
    (index: 2; f: 3; g: 26; k: -11),
    (index: 2; f: 5; g: 2; k: 1),
    (index: 2; f: 5; g: 8; k: 0),
    (index: 2; f: 5; g: 22; k: -7),
    (index: 2; f: 5; g: 28; k: -12),
    (index: 2; f: 7; g: 4; k: 2),
    (index: 2; f: 7; g: 14; k: -1),
    (index: 2; f: 7; g: 16; k: -2),
    (index: 2; f: 7; g: 26; k: -9),
    (index: 2; f: 8; g: 1; k: 3),
    (index: 2; f: 8; g: 11; k: 1),
    (index: 2; f: 8; g: 19; k: -3),
    (index: 2; f: 8; g: 29; k: -11),
    (index: 2; f: 10; g: 7; k: 4),
    (index: 2; f: 10; g: 13; k: 2),
    (index: 2; f: 10; g: 17; k: 0),
    (index: 2; f: 10; g: 23; k: -4),
    (index: 6; f: 1; g: 10; k: -2),
    (index: 6; f: 1; g: 20; k: -7),
    (index: 6; f: 2; g: 7; k: -1),
    (index: 6; f: 2; g: 13; k: -3),
    (index: 6; f: 2; g: 17; k: -5),
    (index: 6; f: 2; g: 23; k: -9),
    (index: 6; f: 3; g: 2; k: 0),
    (index: 6; f: 3; g: 8; k: -1),
    (index: 6; f: 3; g: 22; k: -8),
    (index: 6; f: 3; g: 28; k: -13),
    (index: 6; f: 4; g: 5; k: 0),
    (index: 6; f: 4; g: 25; k: -10),
    (index: 6; f: 6; g: 5; k: 1),
    (index: 6; f: 6; g: 25; k: -9),
    (index: 6; f: 7; g: 2; k: 2),
    (index: 6; f: 7; g: 8; k: 1),
    (index: 6; f: 7; g: 22; k: -6),
    (index: 6; f: 7; g: 28; k: -11),
    (index: 6; f: 8; g: 7; k: 2),
    (index: 6; f: 8; g: 13; k: 0),
    (index: 6; f: 8; g: 17; k: -2),
    (index: 6; f: 8; g: 23; k: -6),
    (index: 6; f: 9; g: 10; k: 2),
    (index: 6; f: 9; g: 20; k: -3),
    (index: 12; f: 1; g: 4; k: -1),
    (index: 12; f: 1; g: 14; k: -4),
    (index: 12; f: 1; g: 16; k: -5),
    (index: 12; f: 1; g: 26; k: -12),
    (index: 12; f: 2; g: 5; k: -1),
    (index: 12; f: 2; g: 25; k: -11),
    (index: 12; f: 3; g: 10; k: -2),
    (index: 12; f: 3; g: 20; k: -7),
    (index: 12; f: 4; g: 1; k: 0),
    (index: 12; f: 4; g: 11; k: -2),
    (index: 12; f: 4; g: 19; k: -6),
    (index: 12; f: 4; g: 29; k: -14),
    (index: 12; f: 6; g: 1; k: 1),
    (index: 12; f: 6; g: 11; k: -1),
    (index: 12; f: 6; g: 19; k: -5),
    (index: 12; f: 6; g: 29; k: -13),
    (index: 12; f: 7; g: 10; k: 0),
    (index: 12; f: 7; g: 20; k: -5),
    (index: 12; f: 8; g: 5; k: 2),
    (index: 12; f: 8; g: 25; k: -8),
    (index: 12; f: 9; g: 4; k: 3),
    (index: 12; f: 9; g: 14; k: 0),
    (index: 12; f: 9; g: 16; k: -1),
    (index: 12; f: 9; g: 26; k: -8),
    (index: 15; f: 1; g: 2; k: -1),
    (index: 15; f: 1; g: 8; k: -2),
    (index: 15; f: 1; g: 22; k: -9),
    (index: 15; f: 1; g: 28; k: -14),
    (index: 15; f: 4; g: 7; k: -1),
    (index: 15; f: 4; g: 13; k: -3),
    (index: 15; f: 4; g: 17; k: -5),
    (index: 15; f: 4; g: 23; k: -9),
    (index: 15; f: 5; g: 4; k: 0),
    (index: 15; f: 5; g: 14; k: -3),
    (index: 15; f: 5; g: 16; k: -4),
    (index: 15; f: 5; g: 26; k: -11),
    (index: 15; f: 6; g: 7; k: 0),
    (index: 15; f: 6; g: 13; k: -2),
    (index: 15; f: 6; g: 17; k: -4),
    (index: 15; f: 6; g: 23; k: -8),
    (index: 15; f: 9; g: 2; k: 3),
    (index: 15; f: 9; g: 8; k: 2),
    (index: 15; f: 9; g: 22; k: -5),
    (index: 15; f: 9; g: 28; k: -10),
    (index: 15; f: 10; g: 1; k: 4),
    (index: 15; f: 10; g: 11; k: 2),
    (index: 15; f: 10; g: 19; k: -2),
    (index: 15; f: 10; g: 29; k: -10)
  );

// squares of primes >= 7, < 240
  qqtab: TArray49 = (
    49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809,
    3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609,
    11449, 11881, 12769, 16129, 17161, 18769, 19321, 22201, 22801, 24649,
    26569, 27889, 29929, 32041, 32761, 36481, 37249, 38809, 39601, 44521,
    49729, 51529, 52441, 54289, 57121
  ) ;

  // (qq * 11 + 1) / 60 or (qq * 59 + 1) / 60
  qq60tab: TArray49 = (
    9, 119, 31, 53, 355, 97, 827, 945, 251, 1653, 339, 405, 515, 3423, 3659,
    823, 4957, 977, 6137, 1263, 7789, 1725, 10031, 1945, 2099, 11683, 2341,
    2957, 16875, 3441, 18999, 21831, 22421, 4519, 4871, 5113, 5487, 31507,
    32215, 35873, 6829, 7115, 38941, 43779, 9117, 9447, 51567, 9953,56169
  );

procedure doit4(a: PLongArray; x, y: LongInt; start: TPrimeType);
var
  i0, y0: LongInt;
  i: LongInt;
  data, pos, bits: LongWord;
begin
  Inc(x, x);
  Inc(x, 15);
  Inc(y, 15);
  Inc(start, 1000000000);
  while (start < 0) do begin
    Inc(start, x);
    Inc(x, 30);
  end;
  Dec(start, 1000000000);
  i:=start;
  while (i < B) do begin
    Inc(i, x);
    Inc(x, 30);
  end;
  while true do begin
    Dec(x, 30);
    if (x <= 15) then exit;
    Dec(i, x);
    while (i < 0) do begin
      Inc(i, y);
      Inc(y, 30);
    end;
    i0 := i; y0 := y;
    while (i < B) do begin
      pos := i;
      data := i;
      pos:=pos shr 5;
      data := data and 31;
      Inc(i, y);
      Inc(y, 30);
      bits := a[pos];
      data := two[data];
      bits := bits xor data;
      a[pos] := bits;
    end;
    i := i0;
    y := y0;
  end;
end;

procedure doit6(a: PLongArray; x, y: LongInt; start: TPrimeType);
var
  i0, y0: LongInt;
  i: LongInt;
  data, pos, bits: LongWord;
begin
  Inc(x, 5);
  Inc(y, 15);
  Inc(start, 1000000000);
  while (start < 0) do begin
    Inc(start, x);
    Inc(x, 10);
  end;
  Dec(start, 1000000000);
  i := start;
  while (i < B) do begin
    Inc(i, x);
    Inc(x, 10);
  end;
  while true do begin
    Dec(x, 10);
    if (x <= 5) then exit;
    Dec(i, x);
    while (i < 0) do begin
      Inc(i, y);
      Inc(y, 30);
    end;
    i0 := i;
    y0 := y;
    while (i < B) do begin
      pos := i;
      data := i;
      pos:= pos shr 5;
      data:=data and 31;
      Inc(i, y);
      Inc(y, 30);
      bits := a[pos];
      data := two[data];
      bits :=bits xor data;
      a[pos] := bits;
    end;
    i := i0;
    y := y0;
  end;
end;

procedure doit12(a: PLongArray; x, y: LongInt; start: TPrimeType);
var
  i0, y0: LongInt;
  i: LongInt;
  data, pos, bits: LongWord;
begin
  Inc(x, 5);
  Inc(start, 1000000000);
  while (start < 0) do begin
    Inc(start, x);
    Inc(x, 10);
  end;
  Dec(start, 1000000000);
  i := start;
  while (i < 0) do begin
    Inc(i, x);
    Inc(x, 10);
  end;
  Inc(y, 15);
  Inc(x, 10);
  while true do begin
    while (i >= B) do begin
      if (x <= y) then exit;
      Dec(i, y);
      Inc(y, 30);
    end;
    i0 := i;
    y0 := y;
    while ((i >= 0) and (y < x)) do begin
      pos := i;
      data := i;
      pos:=pos shr 5;
      data :=data and 31;
      Dec(i, y);
      Inc(y, 30);
      bits := a[pos];
      data := two[data];
      bits :=bits xor data;
      a[pos] := bits;
    end;
    i := i0;
    y := y0;
    Inc(i, x);
    Dec(i, 10);
    Inc(x, 10);
  end;
end;

procedure squarefree1big(buf: PLongArray; base: TPrimeType; q: LongWord; qq: TPrimeType);
var
  i: TPrimeType;
  pos: LongWord;
  n: integer;
  bound: TPrimeType;
begin
  bound := base + 60 * B;
  while (qq < bound) do begin
    if (bound < 2000000000) then
      i := qq - (Cardinal(base) mod Cardinal(qq))
    else
      i := qq - (base mod qq);
    if not Odd(i) then Inc(i, qq);
    if (i < B * 60) then begin
      pos := i;
      n := deltainverse[pos mod 60];
      if (n >= 0) then begin
        pos := pos div 60;
        buf[LongWord(n) + (pos shr 5)]:=buf[LongWord(n) + (pos shr 5)] or two[pos and 31];
      end;
    end;
    Inc(qq, q);
    Inc(q, 1800);
  end;
end;

procedure squarefree1(buf: PLongArray; L: TPrimeType; q: LongWord);
var
  qq: Longword;
  qqhigh: LongWord;
  i: LongWord;
  ilow, ihigh: LongWord;
  n: integer;
  base: TPrimeType;
begin
  base := 60 * L;
  qq := q * q;
  q := 60 * q + 900;

  while (qq < B * 60) do begin
    if (base < 2000000000) then
      i := qq - (LongWord(base) mod qq)
    else
      i := qq - (base mod qq);
    if not Odd(i) then Inc(i, qq);

    if (i < B * 60) then begin
      qqhigh := qq div 60;
      ilow := i mod 60;
      ihigh := i div 60;

      Inc(qqhigh, qqhigh);
      while (ihigh < B) do begin
        n := deltainverse[ilow];
        if (n >= 0) then
          buf[LongWord(n) + (ihigh shr 5)]:=buf[LongWord(n) + (ihigh shr 5)] or two[ihigh and 31];
        Inc(ilow, 2);
        Inc(ihigh, qqhigh);
        if (ilow >= 60) then begin
          Dec(ilow, 60);
          Inc(ihigh);
        end;
      end;
    end;

    Inc(qq, q);
    Inc(q, 1800);
  end;

  squarefree1big(buf,base,q,qq);
end;

procedure squarefree49big(buf: PLongArray; base: TPrimeType; q: LongWord; qq: TPrimeType);
var
  i: TPrimeType;
  pos: LongWord;
  n: integer;
  bound: TPrimeType;
begin
  bound := base + 60 * B;

  while (qq < bound) do begin
    if (bound < 2000000000) then
      i := qq - (Cardinal( base) mod Cardinal(qq))
    else
      i := qq - (base mod qq);
    if not Odd(i) then Inc(i, qq);

    if (i < B * 60) then begin
      pos := i;
      n := deltainverse[pos mod 60];
      if (n >= 0) then begin
        pos := pos div 60;
        buf[LongWord(n) + (pos shr 5)] := buf[LongWord(n) + (pos shr 5)] or two[pos and 31];
      end;
    end;

    Inc(qq, q);
    Inc(q, 1800);
  end;
end;

procedure squarefree49(buf: PLongArray; L: TPrimeType; q: LongWord);
var
  qq: LongWord;
  qqhigh: LongWord;
  i: LongWord;
  ilow, ihigh: LongWord;
  n: integer;
  base: TPrimeType;
begin
  base := 60 * L;

  qq := q * q;
  q := 60 * q + 900;

  while (qq < B * 60) do begin
    if (base < 2000000000) then
      i := qq - (Cardinal(base) mod qq)
    else
      i := qq - (base mod qq);
    if not Odd(i) then Inc(i, qq);

    if (i < B * 60) then begin
      qqhigh := qq div 60;
      ilow := i mod 60;
      ihigh := i div 60;

      Inc(qqhigh, qqhigh);
      Inc(qqhigh, 1);
      while (ihigh < B) do begin
        n := deltainverse[ilow];
        if (n >= 0) then
          buf[LongWord(n) + (ihigh shr 5)]:=buf[LongWord(n) + (ihigh shr 5)] or two[ihigh and 31];
        Inc(ilow, 38);
        Inc(ihigh, qqhigh);
        if (ilow >= 60) then begin
          Dec(ilow, 60);
          Inc(ihigh, 1);
        end;
      end;
    end;

    Inc(qq, q);
    Inc(q, 1800);
  end;

  squarefree49big(buf,base,q,qq);
end;

procedure squarefreetiny(a: PLongArray; const Lmodqq: TArray49; d: Cardinal);
var
  j: integer;
  k, qq, pos, data, bits: LongWord;
begin
  for j:=0 to 48 do begin
    qq := qqtab[j];
    k := qq - 1 - ((Lmodqq[j] + qq60tab[j] * d - 1) mod qq);
    while (k < B) do begin
      pos := k;
      data := k;
      pos :=pos shr 5;
      data:=data and 31;
      Inc(k, qq);
      bits := a[pos];
      data := two[data];
      bits:=bits or data;
      a[pos] := bits;
    end;
  end;
end;

procedure TAtkinSieve.Clear;
begin
  FillChar(buf, SizeOf(buf), not Cardinal(0));
end;

constructor TAtkinSieve.Create;
begin
  Init;
  SkipTo(2);
end;

procedure TAtkinSieve.Fill;
var
  mask: LongWord;
  base: TPrimeType;
  bits0, bits1, bits2, bits3, bits4, bits5, bits6, bits7: LongWord;
  bits8, bits9, bits10, bits11, bits12, bits13, bits14, bits15: LongWord;
begin
  if (pos = B32) then begin
    Generate;
    Inc(L, B);
    pos := 0;
  end;

  bits0 := not buf[0][pos];
  bits1 := not buf[1][pos];
  bits2 := not buf[2][pos];
  bits3 := not buf[3][pos];
  bits4 := not buf[4][pos];
  bits5 := not buf[5][pos];
  bits6 := not buf[6][pos];
  bits7 := not buf[7][pos];
  bits8 := not buf[8][pos];
  bits9 := not buf[9][pos];
  bits10 := not buf[10][pos];
  bits11 := not buf[11][pos];
  bits12 := not buf[12][pos];
  bits13 := not buf[13][pos];
  bits14 := not buf[14][pos];
  bits15 := not buf[15][pos];
  Inc(pos);

  Inc(Fbase, 1920);
  base:=FBase;

  num := 0;

  mask := $80000000;
  while mask>0 do begin
    Dec(base, 60);
    if (bits15 and mask)<>0 then begin
      p[num] := base + 59;
      Inc(num);
    end;
    if (bits14 and mask)<>0 then begin
      p[num] := base + 53;
      Inc(num);
    end;
    if (bits13 and mask)<>0 then begin
      p[num] := base + 49;
      Inc(num);
    end;
    if (bits12 and mask)<>0 then begin
      p[num] := base + 47;
      Inc(num);
    end;
    if (bits11 and mask)<>0 then begin
      p[num] := base + 43;
      Inc(num);
    end;
    if (bits10 and mask)<>0 then begin
      p[num] := base + 41;
      Inc(num);
    end;
    if (bits9 and mask)<>0 then begin
      p[num] := base + 37;
      Inc(num);
    end;
    if (bits8 and mask)<>0 then begin
      p[num] := base + 31;
      Inc(num);
    end;
    if (bits7 and mask)<>0 then begin
      p[num] := base + 29;
      Inc(num);
    end;
    if (bits6 and mask)<>0 then begin
      p[num] := base + 23;
      Inc(num);
    end;
    if (bits5 and mask)<>0 then begin
      p[num] := base + 19;
      Inc(num);
    end;
    if (bits4 and mask)<>0 then begin
      p[num] := base + 17;
      Inc(num);
    end;
    if (bits3 and mask)<>0 then begin
      p[num] := base + 13;
      Inc(num);
    end;
    if (bits2 and mask)<>0 then begin
      p[num] := base + 11;
      Inc(num);
    end;
    if (bits1 and mask)<>0 then begin
      p[num] := base + 7;
      Inc(num);
    end;
    if (bits0 and mask)<>0 then begin
      p[num] := base + 1;
      Inc(num);
    end;
    mask:=mask shr 1;
  end;
end;

procedure TAtkinSieve.Generate;
var
  Lmodqq: TArray49;
  i: integer;
begin
  if (L > 2000000000) then
    for i:=0 to 48 do
      Lmodqq[i] := L mod qqtab[i]
  else
    for i:=0 to 48 do
      Lmodqq[i] := Cardinal(L) mod qqtab[i];

  Clear;

  for i:=0 to 16-1 do
    doit4(@buf[0], for4[i].f,for4[i].g,int64(for4[i].k) - L);
  squarefreetiny(@buf[0],Lmodqq,1);
  for i:=16 to 32-1 do
    doit4(@buf[3],for4[i].f,for4[i].g,int64(for4[i].k) - L);
  squarefreetiny(@buf[3],Lmodqq,13);
  for i:=32 to 48-1 do
    doit4(@buf[4],for4[i].f,for4[i].g,int64(for4[i].k) - L);
  squarefreetiny(@buf[4],Lmodqq,17);
  for i:=48 to 64-1 do
    doit4(@buf[7],for4[i].f,for4[i].g,int64(for4[i].k) - L);
  squarefreetiny(@buf[7],Lmodqq,29);
  for i:=64 to 80-1 do
    doit4(@buf[9],for4[i].f,for4[i].g,int64(for4[i].k) - L);
  squarefreetiny(@buf[9],Lmodqq,37);
  for i:=80 to 96-1 do
    doit4(@buf[10],for4[i].f,for4[i].g,int64(for4[i].k) - L);
  squarefreetiny(@buf[10],Lmodqq,41);
  for i:=96 to 112-1 do
    doit4(@buf[13],for4[i].f,for4[i].g,int64(for4[i].k) - L);
  squarefreetiny(@buf[13],Lmodqq,49);
  for i:=112 to 128-1 do
    doit4(@buf[14],for4[i].f,for4[i].g,int64(for4[i].k) - L);
  squarefreetiny(@buf[14],Lmodqq,53);

  for i:=0 to 12-1 do
    doit6(@buf[1],for6[i].f,for6[i].g,int64(for6[i].k) - L);
  squarefreetiny(@buf[1],Lmodqq,7);
  for i:=12 to 24-1 do
    doit6(@buf[5],for6[i].f,for6[i].g,int64(for6[i].k) - L);
  squarefreetiny(@buf[5],Lmodqq,19);
  for i:=24 to 36-1 do
    doit6(@buf[8],for6[i].f,for6[i].g,int64(for6[i].k) - L);
  squarefreetiny(@buf[8],Lmodqq,31);
  for i:=36 to 48-1 do
    doit6(@buf[11],for6[i].f,for6[i].g,int64(for6[i].k) - L);
  squarefreetiny(@buf[11],Lmodqq,43);

  for i:=0 to 24-1 do
    doit12(@buf[2],for12[i].f,for12[i].g,int64(for12[i].k) - L);
  squarefreetiny(@buf[2],Lmodqq,11);
  for i:=24 to 48-1 do
    doit12(@buf[6],for12[i].f,for12[i].g,int64(for12[i].k) - L);
  squarefreetiny(@buf[6],Lmodqq,23);
  for i:=48 to 72-1 do
    doit12(@buf[12],for12[i].f,for12[i].g,int64(for12[i].k) - L);
  squarefreetiny(@buf[12],Lmodqq,47);
  for i:=72 to 96 do
    doit12(@buf[15],for12[i].f,for12[i].g,int64(for12[i].k) - L);
  squarefreetiny(@buf[15],Lmodqq,59);

  squarefree49(@buf, L, 247);
  squarefree49(@buf, L, 253);
  squarefree49(@buf, L, 257);
  squarefree49(@buf, L, 263);
  squarefree1(@buf, L, 241);
  squarefree1(@buf, L, 251);
  squarefree1(@buf, L, 259);
  squarefree1(@buf, L, 269);
end;

function TAtkinSieve.GetCurrent: TPrimeType;
begin
  Result:=p[num];
end;

procedure TAtkinSieve.Init;
begin
  L := 1;
  FBase := 60;

  pos := PRIMEGEN_WORDS;

  p[0] := 59;
  p[1] := 53;
  p[2] := 47;
  p[3] := 43;
  p[4] := 41;
  p[5] := 37;
  p[6] := 31;
  p[7] := 29;
  p[8] := 23;
  p[9] := 19;
  p[10] := 17;
  p[11] := 13;
  p[12] := 11;
  p[13] := 7;
  p[14] := 5;
  p[15] := 3;
  p[16] := 2;

  num := 17;
end;

function TAtkinSieve.Next: TPrimeType;
begin
  while (num=0) do
    Fill;
  Dec(num);
  Result:=p[num];
end;

procedure TAtkinSieve.SkipTo(v: TPrimeType);
begin
  while true do begin
    while (num<>0) do begin
      if (p[num - 1] >= v) then exit;
      Dec(num);
    end;
    while ((pos < B32) and (FBase + 1920 < v)) do begin
      Inc(FBase, 1920);
      Inc(pos);
    end;
    if (pos = B32) then
      while (FBase + B * 60 < v) do begin
        Inc(L, B);
        Inc(FBase, B*60);
      end;
    Fill;
  end;
end;

end.

unit Eratosthenes;
// Решето Эратосфена
// http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
// Melissa E. O’Neill, The Genuine Sieve of Eratosthenes
// Harvey Mudd College, Claremont, CA, U.S.A. (e-mail: oneill@acm.org)

interface

type
  TPrimeType = Cardinal;

  TEratosthenesSieveLookupTableItem = record
    Value: TPrimeType;
    Next: Cardinal;
    WheelIndex: Cardinal;
    Incrementor: TPrimeType;
  end;

  TEratosthenesSieve = class(TObject)
  private
    FLookupTable: array of TEratosthenesSieveLookupTableItem;
    FLookupTableSize: TPrimeType;
    FLookupTableCapacity: TPrimeType;
    FLookupTableCapacityStep: TPrimeType;
    FWheelIndex: Cardinal;
    FLookupTableLast: Cardinal;
    FLookupTableFirst: Cardinal;
    FCurrent: TPrimeType;
    function LookupAppend: Cardinal;
    function LookupInsert(from, k: Cardinal): Cardinal;
    procedure LookupTableGrow;
    procedure StrikeOut;
    function CheckNext: boolean;
    function Wheel(var WheelIndex: Cardinal): Cardinal;
    procedure Spin;
  protected
    function GetCurrent: TPrimeType;
  public
    constructor Create;
    destructor Destroy; override;
    function Next: TPrimeType;
    property LookupTableCapacityStep: TPrimeType read FLookupTableCapacityStep
      write FLookupTableCapacityStep;
    property Current: TPrimeType read GetCurrent;
  end;

implementation

{ TEratosthenesSieve }

const
  WheelSize = 48;
  Wheel2357: array[0..WheelSize-1] of byte = (
    2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,
    6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10
  );

function Increment(Incrementor: TPrimeType;
  WheelValue: Cardinal): TPrimeType;
// Обходимся без умножения
asm
  // eax = Incrementor
  // edx = WheelValue
    test edx, edx
    jp  @1              // переходим, если 6 или 10
    bsf  ecx, edx        // (2)=1, (4)=2, (8)=3
    shl  eax, cl
    ret
@1: shl  eax, 1
    cmp  edx, 6          // *2
    jnz  @2
    lea  eax, [eax+eax*2] // *3
    ret
@2: lea  eax, [eax+eax*4] // *5
end;

function TEratosthenesSieve.CheckNext: boolean;
begin
  Spin; // Находим следующее число для проверки
  // Если текущее число меньше min(LookupTable), значит оно не "вычеркнуто"
  // и является простым
  Result:=FCurrent<FLookupTable[FLookupTableFirst].Value;
  if Result then
    // Если число простое, добавляем его в LookupTable
    LookupAppend
  else
    // а иначе - просеиваем решето - вычеркиваем следующие числа
    StrikeOut;
end;

constructor TEratosthenesSieve.Create;
const
  PrimeFinderLookupTableCapacityStep = 5000;
begin
  FLookupTableCapacityStep:=PrimeFinderLookupTableCapacityStep;
  FCurrent:=1;
end;

destructor TEratosthenesSieve.Destroy;
begin
  // необязательная финализация, компилятор сделал бы это за нас,
  // но насчет ранних версий Delphi не могу быть уверенным
  SetLength(FLookupTable, 0);
  inherited;
end;

function TEratosthenesSieve.GetCurrent: TPrimeType;
begin
  Result:=FCurrent;
end;

function TEratosthenesSieve.LookupInsert(from, k: Cardinal): Cardinal;
var
  i: Cardinal;
  KValue: TPrimeType;
  KIncrementor: TPrimeType;
begin
  Result:=k;
  with FLookupTable[k] do begin
    KValue:=Value;
    KIncrementor:=Increment(Incrementor, Wheel2357[WheelIndex]);
  end;
  while true do begin
    if from=High(Cardinal) then
      i:=FLookupTableFirst
    else
      i:=FLookupTable[from].Next;
    with FLookupTable[i] do
      if (Value>KValue) or ( (Value=KValue) and
        (Increment(Incrementor, Wheel2357[WheelIndex])>KIncrementor) ) then begin
        FLookupTable[k].Next:=i;
        if from=High(Cardinal) then
          FLookupTableFirst:=k
        else
          FLookupTable[from].Next:=k;
        break;
      end;
    from:=i;
  end;
end;

function TEratosthenesSieve.LookupAppend: Cardinal;
begin
  // при необходимости увеличиваем размер таблицы
  if FLookupTableSize=FLookupTableCapacity then
    LookupTableGrow;
  // добавляем в LookupTable тройку (Current^2, WheelIndex, Current)
  // ведь очевидно, что все значения меньшие чем Current^2 уже "вычеркнуты"
  if FLookupTableLast<>High(Cardinal) then
    FLookupTable[FLookupTableLast].Next:=FLookupTableSize;
  FLookupTableLast:=FLookupTableSize;
  Inc(FLookupTableSize);
  with FLookupTable[FLookupTableLast] do begin
    Value:=FCurrent*FCurrent;
    Next:=High(Cardinal);
    WheelIndex:=FWheelIndex;
    Incrementor:=FCurrent;
  end;
  Result:=FLookupTableLast;
end;

procedure TEratosthenesSieve.LookupTableGrow;
begin
  Inc(FLookupTableCapacity, FLookupTableCapacityStep);
  SetLength(FLookupTable, FLookupTableCapacity);
end;

function TEratosthenesSieve.Next: TPrimeType;
begin
  // Находим следующее простое число
  // Первые несколько чисел задаем явно, это связано с тем, что
  // мы и так исключаем из рассмотрения все числа, кратные 2, 3, 5, 7
  case FCurrent of
    1: FCurrent:=2;
    2: FCurrent:=3;
    3: FCurrent:=5;
    5: FCurrent:=7;
    7:
      begin
        FCurrent:=11;
        FLookupTableFirst:=LookupAppend;
      end;
    else
      repeat until CheckNext; // просеиваем решето, пока не найдем простое ч.
  end;
  Result:=FCurrent;
end;

procedure TEratosthenesSieve.StrikeOut;
// Увеличиваем все вхождения Current в таблицу на Incrementor
// ("вычеркиваем" следующие числа)
// LookupTable суть таблица следующих "вычеркнутых" значений
// заодно находим минимальное из содержащихся в ней значений
// Возможна оптимизация путем использования упорядоченной структуры
var
  k: Cardinal;
  from: Cardinal;
begin
  from:=High(Cardinal);
  repeat
    with FLookupTable[FLookupTableFirst] do begin
      Inc(Value, Increment(Incrementor, Wheel(WheelIndex)));
      k:=FLookupTableFirst;
      FLookupTableFirst:=Next;
      from:=LookupInsert(from, k);
    end;
  until FLookupTable[FLookupTableFirst].Value>Current;
end;

function TEratosthenesSieve.Wheel(var WheelIndex: Cardinal): Cardinal;
// Идея заключается в том, чтобы для ускорения поиска исключить
// из рассмотрения все числа кратные 2, 3, 5 и 7
// Для этого мы используем т.н. колесо (wheel)
begin
  Result:=Wheel2357[WheelIndex];
  Inc(WheelIndex);
  if WheelIndex=WheelSize then WheelIndex:=0;
end;

procedure TEratosthenesSieve.Spin;
// Находим следующее после Current число для проверки на простоту
// С помощью колеса отсеиваем значительную часть чисел для проверки
begin
  Inc(FCurrent, Wheel(FWheelIndex));
end;

end.

procedure GenSimple(MaxSimpleNumber: Integer);
var p: array of Integer;
    k,i,j: Integer;
    b: boolean;
begin
SetLength(p,4);
for j:= 1 to 3 do
  begin
  p[j]:= j;
  ShowMessage(IntToStr(p[j]));
  end;
j:= 3; k:= 3;
While k <= MaxSimpleNumber do
  begin
  i:= 2;
  repeat
    Inc(i);
    if p[i]*p[i] > k then
    begin
      SetLength(p,j+1);
      p[j]:= k;
      ShowMessage(IntToStr(p[j]));
      Inc(j);
      b:= true;
    end else b:= (k div p[i])*p[i] = k;
    until b;
  Inc(k,2);
  end;
end;

procedure TForm1.GenerateClick(Sender: TObject);
begin
GenSimple(100);
end;

program Resheto_Eratosphena;
{$APPTYPE CONSOLE}
var
m,i,n: integer;
a: array [1..30000] of integer;
begin
writeln('Введите верхнюю границу расчета');
readln(m);

for i:=1 to m do
a[i]:=i;

for i:=2 to m do
  begin
  n:=2;
  repeat
      if a[i]<>0 then a[i*n]:=0;
      inc(n);
  until (i*n>m);
  end;

for i:=2 to m do
if a[i]<>0 then write(a[i], ' ');
readln;
end.

program Eratosphen;
{$APPTYPE CONSOLE}
var
  N, I, J: Integer;
  Flag: Boolean;
begin
  //N := 40;
  Readln(N);
  for I := 1 to N do
  begin
    Flag := False;
    if Odd(I) then
    begin
      Flag := True;
      for J := 3 to I div 2 do
        if Odd(J) then
          if (I mod J = 0) then
          begin
            Flag := False;
            Break;
          end;
    end;
    if Flag then
      Writeln(I);
  end;
  Readln;
end.