Perl快速查找素数

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Perl›Perl教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　查找N内的所有素数，首先想到的就是：

　　　　对整数N从2开始到sqrt(N)，进行整除计算，能整除则计算N+1，然后循环。方法简单，但效率低下。1000,000内的素数个数：

#!/usr/bin/perl -w
use strict;
my $num=1000001;
my $count=0;
while($num>1){
    my $i=sqrt($num);
    my $j=2;
    for(;$j<=$i;$j++){
        last if(0==$num%$j);
    }
    $count++ if($j>$i);
    $num-=2;
}
print $count,"\n";

　　　　执行时间：　　　

[root@centos1 pl_script]# time perl test.pl 
78497

real    0m21.230s
user    0m21.150s
sys     0m0.049s

　　对比C程序的同等算法:

#include <stdio.h>
#include <math.h>
#define NUM 1000000
main(){
    int i=3,j=0,cnt=0;
    for(;i<=NUM;i+=2){
        int k=sqrt(i);
        for(j=2;j<=k;j++){
            if(i%j==0)break;
        }
        if(j>k)cnt++;
    }
    printf("%d\n",cnt);
}

　　执行效率:

[root@centos1]# time ./prime
78497

real    0m0.376s
user    0m0.355s
sys     0m0.017s

　　C语言果然快，不算好的算法速度也是杠杠的。

　　改进算法：排除所有素数的倍数，剩下的就是素数了。

　　使用一个数组，下标与1000,000内的数一一对应，

　　1、将数组中所有偶数下标值置0；

　　2、从3开始，将所有3的倍数下标置0；

　　3、循环，将全部素数的倍数下标置0

　　代码如下：

#!/usr/bin/perl -w
use strict;
use constant NUM=>1000000;
# 新建数组，下标与数字一一对应，并排除偶数
my @arr=map{$_%2?$_:0}(0..NUM);
$arr[1]=0;
# 从3开始，排除3的倍数
for(my $i=3;$i<=sqrt(NUM);$i+=2){
    my $k=$i+$i; # n的2倍
    while($k<NUM){
        $arr[$k]=0 if($arr[$k]);
        $k+=$i; # n的N倍
    }
}
# 选出不为0的
@arr=grep{$_}@arr;
print scalar(@arr),"\n";

　　测试输出：

[root@centos1 pl_script]# time perl prime.pl 
78497

real    0m2.714s
user    0m2.422s
sys     0m0.266s

　　C同等算法：

#include <stdio.h>
#include <math.h>
#define NUM 1000000
char arr[NUM+1];
main(){
    int cnt=0,i=0,j=0;
    float k=sqrt(NUM);
    for(i=0;i<=NUM;i+=2)arr[i]=0;
    for(i=1;i<=NUM;i+=2)arr[i]=1;
    for(i=3;i<=k;i+=2)
        for(j=i+i;j<=NUM;j+=i)
            if(arr[j])arr[j]=0;
    for(i=3;i<=NUM;i++)
        if(arr[i])cnt++;
    printf("%d\n",cnt);
}

　　效率如飞：

[root@centos1]# time ./enhance_prime
78497

real    0m0.069s
user    0m0.046s
sys     0m0.022s

　　趣味：正则表达式计算质数：

　　　　^1?$|^(11+?)\1+$

　表达式中有“|”，也就是说这个表达式可以分成两个部分：/^1?$/ 和 /^(11+?)\1+$/

　　第一部分：/^1?$/，其表示匹配“空串”以及字串中只有一个“1”的字符串。

　　第二部分：/^(11+?)\1+$/，这个部分是整个表达式的关键部分。其可以分成两个部分，(11+?) 和\1+$，前半部很简单了，匹配以“11”开头的并重复0或n个1的字符串，后面的部分意思是把前半部分作为一个字串去匹配还剩下的字符串1次或多次（这句话的意思是——剩余的字串的1的个数要是前面字串1个数的整数倍）。

　　要使用这个正规则表达式，需要把自然数转成多个1的字符串，如：2 要写成 “11”， 3 要写成 “111”，以下是perl表达式：

　　perl -e '$|=1;(1x$_)!~/^1?$|^(11+?)\1+$/ && print"$_ " while ++$_'