编制用筛法求1-n(n≤200)以内素数的程序。 分析: 由希腊著名数学家埃拉托色尼提出的所谓"筛法",步骤如下:
①将所有候选数放入筛中;
②找筛中最小数(必为素数)next,放入集合primes中;
③将next的所有倍数从筛中筛去;
④重复②~④直到筛空。
编程时,用集合变量sieve表示筛子,用集合primes存放所有素数。
【参考程序】
program ex10_3;
const n=200;
var sieve,primes:set of 2..n;
next,j:integer;
begin
sieve:=[2..n];{将所有候选数放入筛中}
primes:=[];{素数集合置空}
next:=2;
repeat
{找筛sieve中最小一个数}
while not (next in sieve) do
next:=succ(next);
primes:=primes+[next];{将最小数放入素数集合中}
{将这个素数的倍数从筛中删去}
j:=next;
while j<=n do
begin
sieve:=sieve-[j];
j:=j+next;
end
until sieve=[];
j:=0;
for next:=2 to n do{打印出所有素数}
if next in primes then
begin
write(next:5);
j:=j+1;
primes:=primes-[next];
end;
writeln;
end.