首先声明本人水平有限,仅仅做一下记录,有错的地方请指正,文章垃圾请包容!!
在网上不小心浏览到一篇技术博客,叫做《求质数算法的N种境界(N>10)》,写得很好,有兴趣的读者自己去搜索。然后就想自己去试试这篇博客里写得各种求质数的方法。
不想搭环境,就暂时用了PHP语言,在apache里运行,简易测试一下。
首先明确一下概念
质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,
除了1和它本身以外不再有其他因数的数称为质数。
100以内质数表
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
53 59 61 67 71 73 79 83 89 97
质数的个数是无穷的。
相对的就是合数
合数,数学用语,英文名为Composite number,指自然数中除了能被1和本身整除外,
还能被其他数(0除外)整除的数(如:4,6,8,9,10)。
与之相对的是质数,而1既不属于质数也不属于合数。最小的合数是4。
以下是求100以内的质数算法
//1.最基础的写法
$a = 1;//序号,标识个数
for($i = 2; $i < 101; $i++) {
$primes = 0;
for($k = 1; $k <= $i; $k++)
if($i%$k === 0) $primes++;
if($primes <= 2){ // 能除以1和自身的整数(不包括0)
echo $a . ".{$i}
";
$a++;
}
}
//2.考虑所有数都可以被1整除和
//如果有(除了自身以外的)质因数,那肯定会小于等于 $i/2,所以 $i/2
//这里不能轻易将第一个算法的语句for($k = 1; $k <= $i; $k++)改成
//for($k = 1; $k <= $i/2; $k++); 原因自己试试就知道了
$a = 1;//序号,标识个数
for($i = 2; $i < 101; $i++) {
$primes = 0;
for($k = 2; $k <= $i/2; $k++)
if($i%$k === 0) $primes++;
if($primes <= 0){ // 能除以1和自身的整数(不包括0)
echo $a . ".{$i}
";
$a++;
}
}
//3.进一步想除了2以外,所有可能的质因数都是奇数。
//所以先测试2,然后再测试3到$i/2的所有奇数。
//关键特殊考虑数字2
$a = 1;//序号,标识个数
for($i = 2; $i < 101; $i++) {
$primes = 0;
if($i != 2 && $i%2 === 0) $primes++;
for($k = 3; $k <= $i/2; $k=$k+2) if($i%$k === 0) $primes++;
if($primes <= 0){ // 能除以1和自身的整数(不包括0)
echo $a . ".{$i}
";
$a++;
}
}
//4.其实只要从 2 一直尝试到√x(开平方),就可以了。
$a = 1;//序号,标识个数
for($i = 2; $i < 101; $i++) {
$primes = 0;
if($i != 2 && $i%2 === 0) $primes++;
for($k = 3; $k <= sqrt($i); $k=$k+2) if($i%$k === 0) $primes++;
if($primes <= 0){ // 能除以1和自身的整数(不包括0)
echo $a . ".{$i}
";
$a++;
}
}
//5.其实只要从 2 一直尝试到√x(开平方)其中的所有质数就可以
//算法理论中经常提到的:以空间换时间。就是先存之前的结果再拿来用
//以下本人写得只是用一个数组来实现这个算法,本人技术有限,不知这样是否准确理解原博
//客作者的意图,就当随便看看吧
$arr =array();
$a = 1;//序号,标识个数
for($i = 2; $i < 101; $i++) {
$primes = 0;
if($i != 2 && $i%2 === 0) $primes++;
if(!empty($arr)){
foreach($arr as $key => $value){
if($value <= sqrt($i)){
if($i%$value === 0) $primes++;
}
}
}
if($primes <= 0){ // 能除以1和自身的整数(不包括0)
array_push($arr,$i);
echo $a . ".{$i}
";
$a++;
}
}
接下来,我们做一下简单的性能测试,比较一下各个算法的优劣,仅仅从时间上考虑以下是测试结果
因为算法1,2,3差异性不是很大,不做比较,比较以下1,4,5的优劣
100以内
算法一
[time:0.0009×××752075195]s
算法五
[time:0.0010001659393311]s
结果显示在100以内差异性不大
1000以内
算法一
[time:0.059004068374634]s
算法四
[time:0.004000186920166]s
算法五
[time:0.035001993179321]s
结果显示在1000以内,算法四已经凸显优势了
10000以内
算法一
[time:4.537260055542]s
算法四
[time:0.19901204109192]s
算法五
[time:1.9741129875183]s
结果显示在10000以内,算法一已经不行了
算法五也不行了
100000以内
算法一
[time:542.75104403496]s
算法四
[time:3.6972119808197]s
算法五
[time:164.25539493561]s
结果显示在100000以内,除了算法四可行,其他都不行
总结:开始以为算法五会更胜一筹,不知道是我写法垃圾,还是php数组的底层问题,也可能我不理解空间换时间的本质,所以目前还是算法4最优了。
本人水平有限,仅仅做一下记录,有错的地方请指正,文章垃圾请包容!!