素数判断与筛法

概念讲解

什么是素数？

素数是大于 1 且只能被 1 和自身整除的自然数。

素数判断

试除法

1234567bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

时间复杂度：$O(\sqrt{n})$

素数筛法

埃拉托色尼筛法

1234567891011121314const int N = 1000005;
bool isPrime[N];

void sieve(int n) {
    memset(isPrime, true, sizeof(isPrime));
    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;
            }
        }
    }
}

时间复杂度：$O(n \log \log n)$

线性筛（欧拉筛）

1234567891011121314const int N = 1000005;
bool isPrime[N];
int primes[N], cnt;

void linearSieve(int n) {
    memset(isPrime, true, sizeof(isPrime));
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
}

时间复杂度：$O(n)$

考点分析

初赛考查方式

1. 选择题： 素数判断
2. 程序阅读： 筛法程序
3. 编程题： 素数应用

常见考点

• 素数判断
• 筛法原理
• 时间复杂度

例题精讲

例题 1：素数判断

题目： 7 是素数吗？

解答：

7 只能被 1 和 7 整除，是素数。

例题 2：筛法

题目： 用埃氏筛求 10 以内的素数。

解答：

筛掉 2 的倍数：4, 6, 8, 10
筛掉 3 的倍数：9
剩下：2, 3, 5, 7

练习题

1. 1 是素数吗？

2. 埃氏筛的时间复杂度是多少？

3. 线性筛为什么是线性的？

易错点

⚠️ 注意：

1. 1 不是素数，2 是最小的素数
2. 埃氏筛从 $i \times i$ 开始标记
3. 线性筛保证每个合数只被筛一次
4. 素数判断只需到 sqrt(n)