Perl版筛法求素数（质数）

redraiment

筛法求素数很大程度是一种集合的减法操作，比如找出一个素数“3”，就得把后面所有是3的倍数的数删除。Perl中提供了 grep 操作为此提供了极大的便利，代码如下：

1. #!/usr/bin/perl
   
2. 
   
3. use 5.10.1;
   
4. 
   
5. $n = <STDIN>;
   
6. @buffer = 2 .. $n;
   
7. 
   
8. while ($buffer[0] ** 2 <= $n) {
   
9.         push @primes, shift @buffer;
   
10.         @buffer = grep { $_ % $primes[$#primes] } @buffer;
    
11. }
    
12. 
    
13. say "@primes @buffer";

复制代码

在我的PC上，算10W数量级的还是很快的。

Igawk

有多快？

擂台上高手VB求素数的方法：10亿 400毫秒以内

Igawk

MATLAB版， BASE-6筛法

1. 
   
2. function p = prime6(n)
   
3. %PRIME6 Generate list of prime numbers.
   
4. %   PRIME6(N) is a row vector of the prime numbers less than or
   
5. %   equal to N.
   
6. if length(n)~=1, error('N must be a scalar'); end
   
7. m=floor(n/3); m1=floor(sqrt(n)/3);
   
8. g = 1:m;
   
9. Q=5; T=2;
   
10. for k = 1:m1
    
11.    P=Q; Q=Q+T; T=6-T;
    
12.    if g(k)
    
13.       M=floor((P^2-1)/3);
    
14.       W=floor((P*Q-1)/3);
    
15.       g(M:2*P:m) = 0; g(W:2*P:m) = 0;
    
16.    end
    
17. end
    
18. g=g(g>0); p=[2 3 4*g+1-floor(g/2)*2];
    
19. p=p(p<=n);
    

复制代码

redraiment

2# Igawk
用脚本语言，快的是“开发效率”。