基本算法

一、数论算法

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;
  var t:integer;
  begin
    if a<b then begin
      t:=a;a:=b;b:=t;
    end;
    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=x then break
      else if x mod pr[i]=0 then exit;
    prime:=true;
  end;{prime}
Read More...

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.