来自"NOCOW"

[编辑] 朴素算法

判断n是否为素数: 试除2~n^(1/2)之间所有整数，复杂度O(n^(1/2))

function work(n:integer):boolean;
  var
    i:integer;
  begin
    if n=1 then
      begin
        work:=false;
        exit;
      end;
    if n=2 then
      begin
        work:=true;
        exit;
      end;
    work:=true;
    for i:=2 to trunc(sqrt(n)) do
      if n mod i=0 then
        begin
          work:=false;
          break;
        end;
  end;

[编辑] 常规判定

在朴素的基础上减少不必要的运算只用试除奇数即可。。

（因为如果能被2整除就已经退出了，否则之后除以偶数都可以分解成对应奇数与2乘积）

var
  n,i,x:longint;
procedure kill;
  begin
    writeln('No');
    halt;
  end;
begin
  readln(n);
  if n<=1 then kill;
  if (n mod 2=0) and (n<>2) then kill;
  for i:=1 to trunc(sqrt(n)) div 2 do
    begin
      x:=i*2+1;
      if n mod x=0 then kill;
    end;
  writeln('Yes');
end.

[编辑] 筛法

当数据较大时，可考虑分级运算。

var
  f:array[1..100000000] of boolean;
  i,p,x:longint;
begin
//  n:=100000000;
  for i:=2 to 10000 do
    f[i]:=true;
  p:=1;
  repeat
    p:=p+1;
    if f[p] then
      begin
        x:=p+p;
        while x<=10000 do
          begin
            f[x]:=false;
            x:=x+p;
          end;
      end;
  until p=10000;
  for i:=10001 to 100000000 do
    f[i]:=true;
  p:=1;
  repeat
    p:=p+1;
    if f[p] then
      begin
        x:=p+10000;
        while x<=100000000 do
          begin
            f[x]:=false;
            x:=x+p;
          end;
      end;
  until p=10000;
  for i:=1 to 100000000 do
    if f[i] then write(i:10);
end.