数论算法

数论算法
1．求两数的最大公约数
function gcd(a,b:integer):integer;
begin
  if b=0 then gcd:=a
    else gcd:=gcd (b,a mod b);
end ;
2．求两数的最小公倍数
function lcm(a,b:integer):integer;
begin
  if a<b then swap(a,b);
  lcm:=a;
  while lcm mod b>0 do inc(lcm,a);
end;
3．素数的求法
A.小范围内判断一个数是否为质数：
function prime (n: integer): Boolean;
  var I: integer;
  begin
    for I:=2 to trunc(sqrt(n)) do
    if n mod I=0 then begin
      prime:=false; exit;
    end;
      prime:=true;
  end;
B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：
  procedure getprime;
    var
    i,j:longint;
    p:array[1..50000] of boolean;
    begin
      fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i<50000 do begin
  if p then begin
    j:=i*2;
    while j<50000 do begin
    p[j]:=false;
    inc(j,i);
    end;
  end;
  inc(i);
  end;
  l:=0;
  for i:=1 to 50000 do
  if p then begin
    inc(l);pr[l]:=i;
  end;
end;{getprime}

function prime(x:longint):integer;
    var i:integer;
    begin
      prime:=false;
for i:=1 to l do
  if pr>=x then break
    else if x mod pr=0 then exit;
prime:=true;
end;{prime}