您现在的位置是:首页» windows系统» c++最简单的算法,c语言判断质数

c++最简单的算法,c语言判断质数

2024-07-13 01:56:47
本内容由系统网小编为大家分享,Windows系统安装教程、办公系统、软件怎么使用、软件使用教程、办公软件攻略等信息。前提准备在开始质数的讨论之前,我们先预备一下:质数的定义:若一个正整数除了1和它自身之外不能被任何自然数整除,则该数称为质数

本内容由系统网小编为大家分享,Windows系统安装教程、办公系统、软件怎么使用、软件使用教程、办公软件攻略等信息。

前提准备

在开始质数的讨论之前,我们先预备一下:

质数的定义:若一个正整数除了1和它自身之外不能被任何自然数整除,则该数称为质数,也叫素数。否则为合数 。

由定义可知,所有 小于等于1的数既不是质数,也不是合数 。

质数的分布较为稀疏,对于一个足够大的数S,不超过S的质数大约有个,也就是说每InN个数约有一个质数, 这点读者了解即可。

质数的判断(试除法)

对于质数的判断,最简单也最容易想到的方法就是一个一个的筛选,也叫试除法。

如果要判断一个数N,那么我们要对2~N-1的所有数都筛选一遍吗,显然不用。首先肯定的是N-1肯定不能整除N,那么是否能进一步缩小范围。我先给出答案:2~sqrt(N)

严谨的证明过程如下图:(注释:分别表示向下,向上取整)

那好,利用这个性质,我们就可以写出一下代码:

Code(O(sqrt(N)))

尽管如此,这个代码还是优化了许多,我们单独考虑2这个情况,然后从3开始只枚举奇数。

难道这就是最快的算法吗?

Miller-Robbin算法

其实还有一个更厉害的算法,名为Miller-Robbin算法,要想学会,我们首先需要理解一个定理:

费马小定理:

对于一个质数 p,任意一个自然数a,那么:(mod p)

证明

XTw.com.Cn系统网专业应用软件下载教程,免费windows10系统,win11,办公软件,OA办公系统,OA软件,办公自动化软件,开源系统,移动办公软件等信息,解决一体化的办公方案。

免责声明:本文中引用的各种信息及资料(包括但不限于文字、数据、图表及超链接等)均来源于该信息及资料的相关主体(包括但不限于公司、媒体、协会等机构)的官方网站或公开发表的信息。内容仅供参考使用,不准确地方联系删除处理!

联系邮箱:773537036@qq.com