Algorithm 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Algorithm
标  题: 筛选法
发信站: 哈工大紫丁香 (Wed Aug 13 16:05:35 2003)

需要我们运用筛选法来解决.
   用筛选法解题要遵循以下原则：确定范围, 根据条件, 逐个实验, 筛区不符合条件的

解. 在实际情况下, 如果不符合条件的元素或集合容易求的, 而确定的范围也有限,则可

以优先考虑用筛选法.
下面举一个求某范围内素数例子来说明: 用筛选法求素数时有一个著名的方法叫做Erat

osthenes筛选法.
   方法大致如下:当求1倒100的素数时, 1不是素数,当然划去, 在2到100内划去2的倍数

(不包括2), 再划去3的倍数(不包括3),(由于4已经划去)划去5的倍数,直至划去不超过1

0的倍数,剩下的就都是素数.需要知道的是在初等数论中有有这样的定理: 合数N的不等

于1的最小正因数不大于N的平方根.
在现在的编程语言中一般都提供了集合类型, 可以很好的解决上面的问题.下面是PASCA

L的源程序:
Program Eratosthenes;
Const n=100;
Var sieve,primes:set of 2..n;
  Next,j:integer;
Begin
  Sieve:=[2..n] ;
  Primes:=[];
  Next:=2;
  Repeat
    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
     begin
       if next in primes then
         begin
           write(next:5) ;
           j:=j+1;
           if j>=10 then
             begin writeln; j:=0 end;
         end;
     end;
   writeln;
   readln;
end.

--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.229.162]