php质数乞降技巧_面试官问小灰若何用轨范判断质数

如何快速判断某个数是否为质数？如何再给定区间内筛出所有的质数？

以上两个问题是大厂口试官常常喜好稽核的。
本文采取多种思路，对以上两个问题进行简析。

本文所有的函数参数均默认为自然数。

文章所涉及的代码利用C++措辞，利用的缺省源如下：

#include<cstdio>#include<ciso646>namespaceMain{namespaceSource{typedefshortunsignedinthu;typedefunsignedintuint;typedeflonglongunsignedintllu;}usingnamespaceSource;staticinlineconstvoidmain(){}}signedintmain(){Main::main();return0;}

判断一个非负整数 是否为质数。

根据定义，可以写出如下代码：

staticinlineconstboolisprime(constuinta){if(a==0ora==1)returnfalse;for(registeruinti(2);i<a;++i)if(not(a%i))returnfalse;returntrue;}

韶光繁芜度 ，空间繁芜度 ， 内约可以办理 的问题。

考虑优化。

我们不雅观察一下一个合数 会被哪个数筛掉。
可列出下表（记为表 1）：

筛掉 的数42628293102122142153162182202213222242255262

（左侧为 ，右侧为筛掉 的数。
）

核心代码：

static inline const uint mpf(const uint c) { for (register uint i(2); i < c; ++i) if (not(c % i)) return i; return 0;}

创造筛掉 的数都较小，我们想到，如果在一个比较小的范围内没有 的约数，那是否可以判断 是质数呢？

于是，我们考虑找到一个合数 的最小非 因数的上限。

设 为一个合数，令 为 的最小非 因数，令 ，显然 。

由于 为合数，故 ，故 ，而 为 的最小非 因数，故 。

故 ，。

以是，若 为合数，则 必定有一个不大于 的因数；若 中没有 的因数，则 为质数（ 除外）。

以是列举到 即可。

staticinlineconstboolisprime(constllua){if(a==0ora==1)returnfalse;for(registeruinti(2);1ullii<=a;++i)if(not(a%i))returnfalse;returntrue;}

韶光繁芜度 ，空间繁芜度 ， 内约可以办理 内的问题。

筛出 中的质数，得到一张 的质数表。

可以通过上面 1.2 中的代码判断每个数是否是质数。

staticinlineconstboolisprime(constllua){...}enum{N=1u<<20};staticuintn;staticboolisp[N];staticuintprime[N],cp;staticinlineconstvoidmain(){scanf("%u",&n);for(registeruinti(0);i<n;++i)if(isp[i]=isprime(i))prime[cp++]=i;for(registeruinti(0);i<cp;++i)printf("%u\n",prime[i]);}

韶光繁芜度 ，空间繁芜度 ，由于大部分数为合数，常数较小， 内约可以办理 的问题。

不雅观察表 1，我们创造，筛掉合数的数总是质数。

于是我们猜想：一个合数 的最小非 因数为质数。

证明：若 的不为 的最小因数为 且 并非质数，则 一定有约数 知足 ；此时一定有 ，又 ，故 且 ，与 是 的最小非 因数抵牾。
得证。

于是可以优化一下 isprime 函数。

enum{N=1<<24};staticuintn;staticboolisp[N];staticuintprime[N],cp;staticinlineconstboolisprime(constllua){if(a==0ora==1)returnfalse;for(registeruinti(0);i<cpand1ullprime[i]prime[i]<=a;++i)if(not(a%prime[i]))returnfalse;returntrue;}staticinlineconstvoidmain(){scanf("%u",&n);for(registeruinti(0);i<n;++i)if(isp[i]=isprime(i))prime[cp++]=i;for(registeruinti(0);i<cp;++i)printf("%u\n",prime[i]);}

韶光繁芜度 （由素数定理 中素数密度约为 ），空间繁芜度 ， 内约可以办理 的问题。

图中的曲线分别表示质数数量 pi(n)（蓝）、n / ln n（绿）与 Li(n)（红）。

既然可以用质数判断一个数是否为合数，那为什么不直接用质数筛出合数呢？这样可以减少很多不必要的打算吧。

随意马虎想到，我们从 开始列举，用 isp[i] 表示 之前有没有被筛过，若列举到一个数未被筛过，则其为质数，用之筛去后面的合数。

enum{N=(constuint)4e7};staticuintn;staticboolisp[N];staticuintprime[N],cp;staticinlineconstvoidmain(){scanf("%u",&n);for(registeruinti(0);i<n;++i)isp[i]=true;isp[1]=isp[0]=false;for(registeruinti(0);i<n;++i){if(isp[i]){prime[cp++]=i;for(registeruintj(i);j<n;j+=i)isp[j]=false;}}for(registeruinti(0);i<cp;++i)printf("%u\n",prime[i]);}

韶光繁芜度 ，空间繁芜度 ， 内约可以办理 的问题。

这种方法被称为埃氏筛（埃拉托斯特尼筛法，sieve of Eratosthenes），是一种非常经典的入门筛法。

韶光繁芜度直不雅观证明：

假设素数在区间内按照质数定理的结论均匀分布，将求和转化为积分，可得打算次数约为

2.3 的紧张缺陷是合数被筛出多次，造成韶光繁芜度偏大。

考虑使每个合数 被其最小质因数筛掉。

设大于 的正整数 的最小质因数为 （若 为质数显然有 ），定义 。

考虑列举素数 和大于 的正整数 ，使得 （此时显然 ）。

那么，如果我们能找到一种方法列举出所有这样的数对 ，我们就可以筛出所有合数（即 ）。

比较显然地，有 ，故 等价于 。

于是，我们列举知足 为质数且 的数对 即可。

考虑列举 ，创造确定 后 不太随意马虎列举。

于是考虑列举大于 的正整数 ，确定 后列举质数 ，使得 。

我们确定 后从小到大列举质数 ，则第一个知足 的质数 即为 ，此前列举到的 均知足 。

于是可以写出如下代码：

enum{N=(constuint)2e8};staticuintn;staticboolisp[N];staticuintprime[N],cp;staticinlineconstvoidmain(){scanf("%u",&n);for(registeruinti(0);i<n;++i)isp[i]=true;isp[1]=isp[0]=false;for(registeruinti(2);i<n;++i){if(isp[i])prime[cp++]=i;for(registeruintj(0);j<cpand1ulliprime[j]<n;++j){isp[iprime[j]]=false;if(not(i%prime[j]))break;//把稳到这里列举到了首个知足 i mod prime[j]=0的 j，不能大略地将判断移至 for 语句中。
}}for(registeruinti(0);i<cp;++i)printf("%u\n",prime[i]);}

时空繁芜度 ， 内约可以办理 的问题。

这种方法被称为线性筛法（欧拉筛法，sieve of Euler），是一种非常常用的筛法。

由于这种方法可以方便地区分筛掉合数的两个数之间是否存在倍数关系，故常常可用来筛积性函数。

好了，关于质数的一系列口试问题我们就聊到这里，记得点赞哦~~