素数

素数是这样的正整数：它除了1和本身之外没有别的因数（1不是素数）。素数的判定，有两种方法可以实现：常规判定和筛法。

素数也叫质数。

素数的判断-->暴力试除

function prime_bool(x:longint):boolean;
var i:longint;
begin
  for i:=2 to trunc(sqrt(x)) do 
    if x mod i=0 then exit(false);
  exit(true);
end;

素数的生成-->筛法求素数

  maxnnum=生成质数的范围
  maxprime=对应范围中的质数个数
 
var
  prime:array[0..maxprime]of longint; { 存储质数 }
  bool:array[1..maxnnum]of boolean;  { 存储每个数是不是质数 }
  procedure prime_make;
var
  i,j:longint;
begin
  fillchar(bool,sizeof(bool),true);
  prime[0]:=0;
  i:=2;
  while i<=maxnnum do
  begin    
    if bool[i] then
    begin
      inc(prime[0]);
      prime[prime[0]]:=i;      
      j:=2*i;
      while j<=maxnnum do
      begin
        if bool[i] then bool[j]:=false;
        inc(j,i);
      end;    
    end;
    inc(i);
  end;
end;