查找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," ";
执行时间：
[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 ",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)," ";
测试输出：
[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 ",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 ++$_'