ssh.txt

素数的求法

                                素数的求法
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[i] 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[i] 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[i]>=x then break
                             else if x mod pr[i]=0 then exit;
                         prime:=true;
                              end;{prime}