面试官问小灰：如何用程序判断质数？

Myth丶恋晨 2022-10-18 01:56 73阅读 0赞

> **质数**（Prime number），又称**素数**，指在大于的自然数中，除了和该数自身外，无法被其他自然数整除的数（也可定义为只有与该数本身两个正因数的数）。

> 如何快速判断某个数是否为质数？如何再给定区间内筛出所有的质数？
> 
> 以上两个问题是大厂面试官常常喜欢考察的。本文采用多种思路，对以上两个问题进行简析。
> 
> 本文所有的函数参数均默认为自然数。

--------------------

文章所涉及的代码使用C++语言，使用的缺省源如下：

# include <cstdio>
    # include <ciso646>
    
    namespace Main {
        namespace Source {
            typedef short unsigned int hu;
            typedef unsigned int uint;
            typedef long long unsigned int llu;
        }
        using namespace Source;
        static inline const void main() {}
    }
    
    signed int main() { Main::main(); return 0; }

--------------------

### 问题1：素数判断 ###

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

### 解决方案 1.1 ###

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

static inline const bool isprime(const uint a) {
        if (a == 0 or a == 1) return false;
        for (register uint i(2); i < a; ++i) if (not(a % i)) return false;
        return true;
    }

时间复杂度，空间复杂度，内约可以解决的问题。

###  ###

### 解决方案 1.2 ###

考虑优化。

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

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

> 核心代码：
> 
>     static inline const uint mpf(const uint c) {
>         for (register uint i(2); i < c; ++i) if (not(c % i)) return i;
>         return 0;
>     }

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

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

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

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

故，。

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

所以枚举到即可。

static inline const bool isprime(const llu a) {
        if (a == 0 or a == 1) return false;
        for (register uint i(2); 1ull * i * i <= a; ++i) if (not(a % i)) return false;
        return true;
    }

时间复杂度，空间复杂度，内约可以解决内的问题。

--------------------

###  ###

### 问题2：区间内筛选素数 ###

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

### 解决方案 2.1 ###

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

static inline const bool isprime(const llu a) {...}
    enum { N = 1u << 20 };
    static uint n;
    static bool isp[N];
    static uint prime[N], cp;
    static inline const void main() {
        scanf("%u", &n);
        for (register uint i(0); i < n; ++i) if (isp[i] = isprime(i)) prime[cp++] = i;
        for (register uint i(0); i < cp; ++i) printf("%u\n", prime[i]);
    }

时间复杂度，空间复杂度，由于大部分数为合数，常数较小，内约可以解决的问题。

### 解决方案 2.2    ###

观察表 1，我们发现，筛掉合数的数总是质数。

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

> 证明：若的不为的最小因数为且并非质数，则必然有约数满足；此时必然有，又，故且，与是的最小非因数矛盾。得证。

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

enum { N = 1 << 24 };
    static uint n;
    static bool isp[N];
    static uint prime[N], cp;
    static inline const bool isprime(const llu a) {
        if (a == 0 or a == 1) return false;
        for (register uint i(0); i < cp and 1ull * prime[i] * prime[i] <= a; ++i)
            if (not(a % prime[i])) return false;
        return true;
    }
    static inline const void main() {
        scanf("%u", &n);
        for (register uint i(0); i < n; ++i) if (isp[i] = isprime(i)) prime[cp++] = i;
        for (register uint i(0); i < cp; ++i) printf("%u\n", prime[i]);
    }

时间复杂度（由素数定理中素数密度约为），空间复杂度，内约可以解决的问题。

![fa929461b649a5838c887029677d64ae.png][]

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

### 解决方案 2.3 ###

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

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

![53ec37e883087238519af0870b9399b7.gif][]

enum { N = (const uint)4e7 };
    static uint n;
    static bool isp[N];
    static uint prime[N], cp;
    static inline const void main() {
        scanf("%u", &n);
        for (register uint i(0); i < n; ++i) isp[i] = true; isp[1] = isp[0] = false;
        for (register uint i(0); i < n; ++i) {
            if (isp[i]) {
                prime[cp++] = i;
                for (register uint j(i); j < n; j += i) isp[j] = false;
            }
        }
        for (register uint i(0); i < cp; ++i) printf("%u\n", prime[i]);
    }

时间复杂度，空间复杂度，内约可以解决的问题。

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

> 时间复杂度直观证明：
> 
> 假设素数在区间内按照质数定理的结论均匀分布，将求和转化为积分，可得计算次数约为

### 解决方案 2.4 ###

2.3 的主要缺点是合数被筛出多次，造成时间复杂度偏大。

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

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

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

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

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

**于是，我们枚举满足为质数且的数对即可。**

考虑枚举，发现确定后不太容易枚举。

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

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

于是可以写出如下代码：

enum { N = (const uint)2e8 };
    static uint n;
    static bool isp[N];
    static uint prime[N], cp;
    static inline const void main() {
        scanf("%u", &n);
        for (register uint i(0); i < n; ++i) isp[i] = true; isp[1] = isp[0] = false;
        for (register uint i(2); i < n; ++i) {
            if (isp[i]) prime[cp++] = i;
            for (register uint j(0); j < cp and 1ull * i * prime[j] < n; ++j) {
                isp[i * prime[j]] = false;
                if (not(i % prime[j])) break;
                // 注意到这里枚举到了首个满足 i mod prime[j] = 0 的 j，不能简单地将判断移至 for 语句中。
            }
        }
        for (register uint i(0); i < cp; ++i) printf("%u\n", prime[i]);
    }

时空复杂度，内约可以解决的问题。

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

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

好了，关于质数的一系列面试问题我们就聊到这里，记得一键三连哦~~

[fa929461b649a5838c887029677d64ae.png]: /images/20221014/a3246492a8764d079dd3bbb7e6b80cd3.png
[53ec37e883087238519af0870b9399b7.gif]: /images/20221014/d8c4b11ff91d44058a1d74875b2d59f2.png