如何快速统计素数个数？——从筛苹果到素数定理

你有没有想过，在1到1000之间到底有多少个素数？如果手动一个个检查，简直要累死。但数学家早就发现，素数的分布其实是有规律的——它们越往后越稀疏，而且可以用一个简单的公式来估算。今天我们就来学习如何用“筛法”快速统计素数个数，并一探素数分布的奇妙秘密。

一、果园里的好苹果——什么是素数计数？

想象你有一个巨大的果园，里面种了无数苹果树，每棵树上结满了苹果，每个苹果上标着数字：1, 2, 3, 4, 5, ... 直到数不清。现在，你想把那些“完美无瑕”的苹果挑出来——所谓“完美无瑕”，就是这个数字除了1和它本身以外，没有别的因数。这样的数字叫素数（也叫质数），比如2、3、5、7、11。而4（能被2整除）、6（能被2和3整除）、9（能被3整除）就不是素数。

老板问你：“小朋友，从1号到100号果树，一共有多少个‘完美苹果’？”你当然可以一个一个检查，但如果是10000个、1000000个呢？我们需要一个聪明的办法，快速知道有多少个素数。这个“有多少个”的问题，就是素数计数问题。

数学家们用一个专门的符号 $\pi(x)$ 来表示“不超过 $x$ 的素数的个数”。注意，这里的 $\pi$ 是希腊字母，和圆周率3.14159…没关系，只是约定俗成的符号。例如：

• $\pi(10) = 4$（素数：2,3,5,7）
• $\pi(100) = 25$
• $\pi(1000) = 168$
• $\pi(1\,000\,000) = 78\,498$

二、快速统计的秘诀——埃拉托斯特尼筛法

要得到 $\pi(x)$，最直接的想法是：从2到x，逐个判断每个数是不是素数。判断一个数 $n$ 是不是素数，需要检查从2到 $\sqrt{n}$ 的所有数是否能整除 $n$。这种方法叫“试除法”。对于单个数字很快，但要统计很多个数，比如1到100万个，每个数都要试除，速度就很慢了。

两千多年前，古希腊数学家埃拉托斯特尼就想出了一个更聪明的办法，就像用一个筛子把合数全部筛掉，剩下的就是素数。我们来看一个“筛苹果”的例子：

1. 先写出从2到20的所有整数：
   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2. 从最小的素数2开始，把2的倍数（4,6,8,10,12,14,16,18,20）全部划掉（标记为合数）。
3. 找到下一个没有被划掉的数——3，它一定是素数。然后把3的倍数（6,9,12,15,18）划掉（注意6和12已经在第2步被划掉，但再划一次也没关系）。
4. 下一个未被划掉的数是5（因为4已经被划掉了），把5的倍数（10,15,20）划掉。
5. 再下一个未被划掉的数是7，把7的倍数（14）划掉。此时7的平方（49）已经大于20，所以停止。
6. 最后所有未被划掉的数就是素数：2,3,5,7,11,13,17,19。一共8个，所以 $\pi(20)=8$。

这种方法就是埃拉托斯特尼筛法（简称埃氏筛）。它的神奇之处在于：我们只用一次遍历，就能得到所有素数。统计未被划掉的个数，就是 $\pi(x)$。时间复杂度大约 $O(x \log \log x)$，对于 $x=10^7$ 也能在1秒内完成。

小提示：为什么内层循环从 $i^2$ 开始？因为比 $i^2$ 小的 $i$ 的倍数（比如 $2i, 3i, \dots$）已经被更小的素数标记过了。例如当 $i=3$ 时，$3 \times 2 = 6$ 已经在 $i=2$ 时被标记，所以我们直接从 $3^2=9$ 开始。

三、素数越往后越稀疏——素数定理

老板还发现了一个有趣现象：最初几步，比如1到10之间，有4个素数（2,3,5,7），看起来蛮多的。可是越往后走，素数似乎变得越来越稀少了。比如1到100之间有25个素数，1到1000之间有168个素数，1到10000之间有1229个素数。素数的密度（即素数个数除以总个数）从10%降到16.8%又降到12.29%……它到底会降到多低？会不会最后完全没有素数了？

数学家们经过长期摸索，发现了一个惊人的规律：当 $x$ 越来越大时，$\pi(x)$ 大约等于 $x / \ln(x)$。这里 $\ln(x)$ 是 $x$ 的自然对数（在数学中常用 $\log x$ 表示自然对数）。用公式写就是：

“$\sim$”读作“渐近于”，意思是它们的比值越来越接近1，但并不是精确相等。这个定理叫做素数定理，是数论里最重要的成果之一。

我们用实际数据验证一下：

可以看到，比值越来越接近1。素数定理告诉我们：在很大的范围内，素数出现的概率大约是 $1/\ln x$。比如 $x=10^9$，$\ln(10^9) \approx 20.7$，所以平均每21个数中才有一个素数，确实很稀疏。这个结果也印证了“素数有无穷多个，但越往后越难找”的直觉。

直观理解：一个数 $n$ 是素数的条件是它不能被小于它的任何素数整除。随着 $n$ 增大，之前遇到的素数越来越多，这些“障碍”越来越多，所以新的素数出现就越来越难了。数学上通过复杂的分析，可以证明密度大约为 $1/\ln x$。

四、动手编程实现——C++和Python代码

4.1 C++实现（埃氏筛）

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 函数：计算小于等于n的素数个数
int countPrimes(int n) {
    if (n < 2) return 0;          // 没有素数
    // 创建布尔数组，长度n+1，初始全部设为true（假设都是素数）
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;  // 0和1不是素数

    // 外层循环从2开始，到sqrt(n)为止
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {            // 如果i是素数
            // 从i*i开始标记合数，步长为i
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;  // 标记为合数
            }
        }
    }

    // 统计true的个数
    int count = 0;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) count++;
    }
    return count;
}

// 扩展：打印所有素数（当n较小时用）
void printPrimes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; ++i)
        if (isPrime[i])
            for (int j = i * i; j <= n; j += i)
                isPrime[j] = false;

    cout << "素数列表: ";
    for (int i = 2; i <= n; ++i)
        if (isPrime[i]) cout << i << " ";
    cout << endl;
}

int main() {
    int x;
    cout << "请输入一个正整数x: ";
    cin >> x;

    int pi = countPrimes(x);
    cout << "小于等于" << x << "的素数个数为: " << pi << endl;

    // 验证素数定理：计算 x / ln(x) 的近似值
    double approx = x / log(x);   // log是自然对数（ln）
    cout << "素数定理近似值 x/ln(x) = " << approx << endl;
    cout << "实际与近似的比值: " << pi / approx << endl;

    // 如果x不大，展示具体素数
    if (x <= 1000) {
        printPrimes(x);
    }
    return 0;
}

4.2 Python实现

import math

def count_primes(n):
    """返回小于等于n的素数个数（埃氏筛）"""
    if n < 2:
        return 0
    # 初始化列表，长度n+1，全部标记为True（假设是素数）
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0和1不是素数

    # 外层循环到 sqrt(n) 即可
    for i in range(2, int(math.isqrt(n)) + 1):
        if is_prime[i]:
            # 从 i*i 开始标记，步长为 i
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    # 统计True的个数（True算1，False算0）
    count = sum(is_prime)
    return count

def print_primes(n):
    """打印所有素数（当n较小时使用）"""
    if n < 2:
        print("None")
        return
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    primes = [i for i in range(2, n+1) if is_prime[i]]
    print("素数列表:", primes)

# 主程序
x = int(input("请输入一个正整数x: "))
pi = count_primes(x)
print(f"小于等于{x}的素数个数为: {pi}")

# 验证素数定理
approx = x / math.log(x)  # math.log是自然对数ln
print(f"素数定理近似值 x/ln(x) = {approx:.2f}")
print(f"实际与近似的比值: {pi / approx:.4f}")

# 如果x不太大，展示具体素数
if x <= 1000:
    print_primes(x)

代码小贴士：

• math.isqrt(n) 返回整数平方根，比 int(math.sqrt(n)) 更精确，避免浮点误差。
• Python 中 sum(is_prime) 可以直接统计 True 的个数，非常简洁。
• 别忘了在 C++ 中引入 <cmath> 才能使用 log 函数。

五、新手常见错误

在实现筛法时，初学者常会踩到下面几个坑，我们一个一个来看：

5.1 数组长度忘记加1

比如要筛到 $n=100$，数组需要能访问下标0到100，所以长度应为 n+1。如果写成 vector<bool> isPrime(n);，则下标 isPrime[n] 越界。

5.2 外层循环条件写错

正确写法是 i * i <= n，而不是 i * i < n 或 i <= sqrt(n)（后者如果写成 int s = sqrt(n) 可能因为浮点误差少算1）。直接写 i * i <= n 最安全。

5.3 内层循环起始点写错

有人从 j = i 或 j = 2*i 开始，这样会导致重复标记。例如 i=3 时，如果从 j=3 开始，会把3本身也标记为合数（错误！）。正确做法是从 j = i*i 开始，因为比 i*i 小的倍数已经被更小的素数处理过了。

5.4 忘记处理0和1

0和1不是素数，一定要在初始化后手动设置 isPrime[0]=isPrime[1]=false。

5.5 整型溢出

当 n 很大时（比如 10^9），i*i 可能会超过 int 的范围（约 21亿）。在 C++ 中，如果 i 是 int，i*i 可能溢出导致死循环。一种解决方法是使用 long long，或者在循环条件中写成 i <= sqrt(n) 并用 double 比较。对于初学者，建议先将 n 控制在 10^7 以内，等学更深后再处理大数。

5.6 统计个数时范围搞错

统计时一定要从2开始（或从0开始但跳过0和1），如果写成 for (int i=0; i<=n; ++i) 并且 isPrime[0] 没处理好，会统计进去。

六、完整示例运行

假设我们运行 C++ 程序，输入 x = 100，输出如下：

请输入一个正整数x: 100
小于等于100的素数个数为: 25
素数定理近似值 x/ln(x) = 21.7147
实际与近似的比值: 1.15129
素数列表: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

可以看到实际有25个素数，而素数定理给出约21.7个，比值约1.15。随着x增大，比值会越来越接近1。

试试更大的数：如果输入 x = 1000000，程序会输出 78498，近似值 72382.4，比值 1.084。注意，此时素数列表就不打印了，因为太多了（几万个）。

七、相关知识点指引

学会了用埃氏筛统计素数个数，你可以继续探索以下内容：

1. 线性筛（欧拉筛）：埃氏筛中每个合数可能被多个素数标记（例如12被2和3各标记一次），而线性筛可以保证每个合数只被它的最小质因子标记一次，速度更快，适合大范围。
2. 分段筛：当要统计的 $x$ 非常大（比如 $10^{12}$）时，无法一次性开出那么大的布尔数组，可以用“分段筛”的思想，只筛出需要的一段。
3. 素数测试：判断一个单独的大数是否为素数，可以用 Miller-Rabin 素性测试（随机算法），它在密码学中广泛使用。
4. 素数在密码学中的应用：RSA 加密算法的安全性就依赖于大素数分解的困难性，所以统计大范围内的素数个数、生成大素数都是信息安全的基础。
5. 更精确的素数计数公式：素数定理只是 $\pi(x)$ 的渐近公式，更精确的公式是 $\pi(x) = \operatorname{Li}(x) + \text{误差}$，其中 $\operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t}$ 是对数积分函数。

希望这篇文章能帮助你理解素数的分布规律，并能动手用代码“数一数”它们。下次老师在数学课上提到“素数有无穷多个”时，你不仅可以自信地点头，还可以用编程快速验证一下：从1数到1亿，到底有多少个素数？答案大约是 5 761 455 个——这是用埃氏筛和素数定理一起告诉我们的秘密。