Count Primes

给定一个大于 1 的正整数 n,计算 2~n 的素数的个数。


1 素数的性质

  • 1 既不是素数,又不是合数。
  • 一个合数 n,必定可以分解为小于等于 sqrt(n)的数(大于等于 2)与大于等于 sqrt(n) 的数(小于 n)的积。也就是说,一个合数,一定存在小于等于 sqrt(n) 的因子。事实上,由于一个合数总能够分解成多个素数的乘积,因此,一个合数,一定存在小于等于 sqrt(n) 的素数因子。

对于判定一个数是否为素数: 若一个数 n 存在 2 至 sqrt(n) 的因子(或者是素数因子),则这个数一定为合数;若不存在,则这个数一定为素数。

对于查找 2 至 n 内的素数: 只需要去掉 2 至 n 中 2 至 sqrt(n) 内的所有素数的倍数即可。

2 分析证明

将 2 至 n 的序列表示为 2, 3, 4, ..., m, ..., n. 根据上面判定一个数是否为素数的方法,则要判定 n 是否为素数,则只需要判定 n 是否存在 2 至 sqrt(n) 的因子(或者素数因子)即可。同样,要判定 m 是否为素数,则只需要判定 m 是否存在 2 至 sqrt(m) 的因子(或者素数因子)即可。m 比 n 要小,事实上,这里只要取一个最大范围,也即 2 至 sqrt(n) 即可。此时,若 2 至 n 内的一个数是 2 至 sqrt(n) 内某个数(或者素数)的倍数,则这个数一定是合数。因此,只需要从 2 至 n 中去掉 2 至 sqrt(n) 内所有数(或者所有素数)的倍数,就能得到 2 至 n 中的所有素数。

3 埃氏筛选法及其优化

上面的这个方法叫做埃氏筛选法 (Sieve of Eratosthenes)。在实现时,还可以做进一步的优化。在删除某一个素数 p 的倍数时,由于 p 的 2 至 (p - 1) 的倍数在删除 2 至 (p - 1) 时的倍数时就已经被删掉,因此每次删除某个素数的倍数时,都是从这个素数的平方,即 (p * p) 开始进行删除,然后删除 (p * (p + 1))...... 假设寻找( 2 至 25 内的素数)。具体实现细节如下:

  • 初始时为:2, 3, 4, 5, 6, 7, 8, 9, 10.
  • 这个序列的第一个数是 2,将其标记为一个素数。然后在余下的序列中删除 2 的倍数的数(从 2 的平方,即 4 开始删除)。删除后余下的序列为:3, 5, 7, 9.
  • 这个序列的第一个数是 3,将其标记为一个素数(事实上,每次开始时,序列的第一个数肯定是素数。否则,它肯定存在一个小于它的素数因子 a,但是,在去除 a 的倍数的时候,就必须要把这个数删除,而现在还存在于序列中,因此,这个数一定为素数)。然后在余下的序列中删除 3 的倍数(从 3 的平方,即 9 开始删除)。删除后余下的序列为:5, 7.
  • 由于 5 > sqrt(10),因而结束循环,查找完毕。 最后得到的所有素数为:2, 3, 5, 7.

在实现过程中,由于要保存 2 至 n 的所有数的信息(bool 类型,表示是否为素数),当 n 较大时,可能会导致空间不足,因此可采用 bitmap 或者 bitset 存储这些信息。

4 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
public:
// 计算 2 至 n - 1 内的素数个数。
int countPrimes(int n)
{
// 存储 2 至 n - 1 内所有数的信息(表示是否为素数)。
// 其中,第 0 个和第 1 个元素为 false,余下每个元素的下标 n 对应数字 n 的信息,初始为 true。
vector<bool> isPrime(n, true);
isPrime[0] = false;
isPrime[1] = false;

// 去除 2 至 n 中 2 至 sqrt(n) 内的素数的倍数。
for(int i = 2; i * i <= n; i++)
{
// 这里是要去除素数的倍数。若为合数,则直接跳过。
if(!isPrime[i])
continue;

// 从素数的平方开始去除。将它的这些倍数对应的 isPrime 元素置为 false。
for(int j = i * i; j <= n; j += i)
isPrime[j] = false;
}

// count 是 algorithm 内的一个函数,用以计数。这里表示计数 isPrime 内 true 的个数。
return count(isPrime.begin(), isPrime.end(), true);
}
};



int main(int argc, char const *argv[])
{
Solution s;

cout << s.countPrimes(10000) << endl;

return 0;
}

Reference