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

小灰

发布于 2022-09-01 15:56:31

9440

发布于 2022-09-01 15:56:31

文章被收录于专栏：程序员小灰

质数（Prime number），又称素数，指在大于 1的自然数中，除了 1和该数自身外，无法被其他自然数整除的数（也可定义为只有1 与该数本身两个正因数的数）。
如何快速判断某个数是否为质数？如何再给定区间内筛出所有的质数？以上两个问题是大厂面试官常常喜欢考察的。本文采用多种思路，对以上两个问题进行简析。本文所有的函数参数均默认为自然数。

文章所涉及的代码使用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：素数判断

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

解决方案 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;
}

时间复杂度 \mathcal O(a) ，空间复杂度 \mathcal O(1) ，1 \operatorname s 内约可以解决 a \in [0, 10^9) 的问题。

解决方案 1.2

考虑优化。

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

	筛掉的数
4	2
6	2
8	2
9	3
10	2
12	2
14	2
15	3
16	2
18	2
20	2
21	3
22	2
24	2
25	5
26	2

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

核心代码：

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

发现筛掉

的数都较小，我们想到，如果在一个比较小的范围内没有 a

的约数，那是否可以判断 a 是质数呢？

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

设 c 为一个合数，令 x 为 c 的最小非 1 因数，令 y = \frac c x ，显然 x \mid c \land y \mid c \land c = xy 。

由于 c 为合数，故 1 < x < c ，故 y > 1 ，而 x 为 c 的最小非 1 因数，故 y \geqslant x 。

故 c = xy \geqslant x^2 ，x \leqslant \sqrt c 。

所以，若 a 为合数，则 a 必定有一个不大于 \sqrt a 的因数；若 (1, \sqrt a] 中没有 a 的因数，则 a 为质数（0, 1 除外）。

所以枚举到 \sqrt a 即可。

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;
}

时间复杂度 \mathcal O(\sqrt a) ，空间复杂度 \mathcal O(1) ，1 \operatorname s 内约可以解决 n \in [0, 10^{18}) 内的问题。

问题2：区间内筛选素数

筛出 [0, n) 中的质数，得到一张 [0, n) 的质数表。

解决方案 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]);
}

时间复杂度 \mathcal O(n^\frac 3 2) ，空间复杂度 \mathcal O(n) ，由于大部分数为合数，常数较小，1 \operatorname s 内约可以解决 n \in [0, 1.5 \times 10^6) 的问题。

解决方案 2.2

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

于是我们猜想：一个合数的最小非 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]);
}

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

解决方案 2.3

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

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

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]);
}

时间复杂度 \mathcal O(n \log \log n) ，空间复杂度 \mathcal O(n) ，1 \operatorname s 内约可以解决 n \in [0, 4 \times 10^7) 的问题。

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

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

T(n) \sim \sum_{p \in \mathbf{Prime} \land p \leqslant n} \frac n p \sim \int_1^n \frac 1 {\ln x} \cdot \frac n x \cdot \operatorname d x \sim n \int_1^n \frac {\operatorname d x} {x \ln x} \sim n \log \log n.

解决方案 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]);
}

时空复杂度 \mathcal O(n) ，1 \operatorname s 内约可以解决 n \in [0, 10^8) 的问题。

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

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

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-06-04，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自程序员小灰微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

c++

登录后参与评论

0 条评论

热度