查找N内的所有素数,首先想到的就是:
对整数N从2开始到sqrt(N),进行整除计算,能整除则计算N+1,然后循环。方法简单,但效率低下。1000,000内的素数个数:
#!/usr/bin/perl -w
use strict;
my $num=;
my $count=;
while($num>){
my $i=sqrt($num);
my $j=;
for(;$j<=$i;$j++){
last if(==$num%$j);
}
$count++ if($j>$i);
$num-=;
}
print $count,"\n";
执行时间:
[root@centos1 pl_script]# time perl test.pl real 0m21.230s
user 0m21.150s
sys 0m0.049s
对比C程序的同等算法:
#include <stdio.h>
#include <math.h>
#define NUM 1000000
main(){
int i=,j=,cnt=;
for(;i<=NUM;i+=){
int k=sqrt(i);
for(j=;j<=k;j++){
if(i%j==)break;
}
if(j>k)cnt++;
}
printf("%d\n",cnt);
}
执行效率:
[root@centos1]# time ./primereal 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=>;
# 新建数组,下标与数字一一对应,并排除偶数
my @arr=map{$_%?$_:}(..NUM);
$arr[]=;
# 从3开始,排除3的倍数
for(my $i=;$i<=sqrt(NUM);$i+=){
my $k=$i+$i; # n的2倍
while($k<NUM){
$arr[$k]= if($arr[$k]);
$k+=$i; # n的N倍
}
}
# 选出不为0的
@arr=grep{$_}@arr;
print scalar(@arr),"\n";
测试输出:
[root@centos1 pl_script]# time perl prime.pl real 0m2.714s
user 0m2.422s
sys 0m0.266s
C同等算法:
#include <stdio.h>
#include <math.h>
#define NUM 1000000
char arr[NUM+];
main(){
int cnt=,i=,j=;
float k=sqrt(NUM);
for(i=;i<=NUM;i+=)arr[i]=;
for(i=;i<=NUM;i+=)arr[i]=;
for(i=;i<=k;i+=)
for(j=i+i;j<=NUM;j+=i)
if(arr[j])arr[j]=;
for(i=;i<=NUM;i++)
if(arr[i])cnt++;
printf("%d\n",cnt);
}
效率如飞:
[root@centos1]# time ./enhance_primereal 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 ++$_’