求质数的各个算法比较

QLQ 发布于2019-06-27 16:17 / 3452人阅读

摘要：首先明确一下概念质数又称素数，有无限个。质数定义为在大于的自然数中，除了和它本身以外不再有其他因数的数称为质数。以内质数表质数的个数是无穷的。

首先声明本人水平有限，仅仅做一下记录，有错的地方请指正，文章垃圾请包容！！

在网上不小心浏览到一篇技术博客，叫做《求质数算法的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.00099992752075195]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最优了。

本人水平有限，仅仅做一下记录，有错的地方请指正，文章垃圾请包容！！

GPU云服务器云服务器最快比较排序算法字符串比较大小算法字符串比较最快算法字符串相似度比较算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/22822.html

电影里的代码之《机械姬》：筛法求质数

摘要：影片处出现了一段代码，细看了一下，发现是筛法求质数的代码，写得非常简练的。重点还是前面的两个函数实现的筛法求质数。今天看了《机械姬》，探讨人工智能话题的电影，豆瓣评分7.5，还是蛮不错的一部电影。影片1:09:29处出现了一段python代码，细看了一下，发现是筛法求质数的python代码，写得非常简练的。先贴个电影的截图： showImg(https://segmentfault....

simon_chen 2019-07-24 18:19 评论0 收藏0
Dubbo 源码分析 - 集群容错之 LoadBalance

摘要：即服务提供者目前正在处理的请求数一个请求对应一条连接最少，表明该服务提供者效率高，单位时间内可处理更多的请求。此时应优先将请求分配给该服务提供者。初始情况下，所有服务提供者活跃数均为。 1.简介 LoadBalance 中文意思为负载均衡，它的职责是将网络请求，或者其他形式的负载均摊到不同的机器上。避免集群中部分服务器压力过大，而另一些服务器比较空闲的情况。通过负载均衡，可以让每台服务...

ybak 2019-08-16 13:53 评论0 收藏0
算法之旅 | 选择排序法

摘要：由于排序的算法有很多，在本次算法系列的分享当中，我们先从简单易上手的选择排序法开始，其它的排序算法会随后陆续跟大家一起分享。 HTML5学堂-码匠：数据快速的计算与排序，与前端页面性能有直接的关系。由于排序的算法有很多，在本次算法系列的分享当中，我们先从简单易上手的选择排序法开始，其它的排序算法会随后陆续跟大家一起分享。算法的基本概念算法是什么，它有何作用为解决一个问题而采取的方...

liaorio 2019-08-20 18:52 评论0 收藏0
OpenCV实战 | 八种目标跟踪算法

摘要：目标追踪首先，我们会大致介绍八种建立在上的目标跟踪算法。词典包含了种的目标追踪器行。它将目标追踪器的命令行参数字符串映射到实际的追踪器函数上。其中行里的目的是根据追踪器命令行参数以及从得来的相关重要信息。虽然我们熟知的的质心追踪器表现得很好，但它需要我们在输入的视频上的每一帧运行一个目标探测器。对大多数环境来说，在每帧上进行检测非常耗费计算力。所以，我们想应用一种一次性的目标检测方法，然后...

shevy 2019-04-25 18:29 评论0 收藏0