质数筛法 - 数学基础

1. 埃拉托斯特尼筛法

从 2 开始，将每个质数的倍数都标记为合数。未被标记的数即为质数。

时间复杂度： $$ O(n \log \log n) $$ —— 非常接近线性时间，效率极高。

范围 (Max N):

点击"开始筛选"


bool is_prime[101];
memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;

for (int i = 2; i * i <= n; i++) {
    if (is_prime[i]) {
        for (int j = i * i; j <= n; j += i)
            is_prime[j] = false; // 标记
    }
}

2. 线性筛法（欧拉筛）

核心思想：每个合数只被它最小的质因子标记一次，保证线性复杂度。

时间复杂度： $$ O(n) $$ —— 真正的线性时间，是最优的筛法。

范围 (Max N):

点击"开始筛选"

已发现的质数：-


bool is_prime[101];
int primes[101], cnt = 0;
memset(is_prime, true, sizeof(is_prime));

for (int i = 2; i <= n; i++) {
    if (is_prime[i]) primes[cnt++] = i;
    for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
        is_prime[i * primes[j]] = false;
        if (i % primes[j] == 0) break; // 关键：确保每个合数只被最小质因子标记
    }
}