姚令武 2025-12-10 07:10 采纳率: 98.5%
浏览 0
已采纳

欧拉筛法去重逻辑如何实现？

在使用欧拉筛法（线性筛）求解素数时，如何确保每个合数仅被其最小的质因数筛去一次，从而实现高效的去重逻辑？常见问题是：为何在遍历已筛出的质数列表时，一旦发现当前数能被某个质数整除就立即跳出循环？这一条件判断如何保证每个合数只被标记一次？理解该机制对掌握欧拉筛法的线性时间复杂度至关重要。请结合内层循环中的取模判断（i % primes[j] == 0）解释其去重原理。
  • 写回答

1条回答 默认 最新

  • 爱宝妈 2025-12-10 09:23
    关注
    <html></html>

    一、欧拉筛法（线性筛）中去重机制的深度解析

    在素数筛法的发展历程中，埃拉托斯特尼筛法（埃氏筛）虽简单直观，但其时间复杂度为 O(n log log n)，在处理大规模数据时存在性能瓶颈。而欧拉筛法（又称线性筛）通过巧妙的去重机制，将时间复杂度优化至 O(n)，实现了每个合数仅被其最小质因数筛除一次的目标。本文将从浅入深，系统剖析其核心逻辑。

    1. 基本原理与算法结构

    • 欧拉筛法维护一个素数列表 primes[] 和一个布尔数组 is_composite[] 来标记合数。
    • 外层循环遍历从 2 到 n 的每一个整数 i。
    • 内层循环遍历已筛出的素数 primes[j]，并用其去筛除 i * primes[j]。
    • 关键判断条件：if (i % primes[j] == 0) break;
    
// 欧拉筛法伪代码示例
vector<int> primes;
bool is_composite[MAXN] = {false};

for (int i = 2; i <= n; i++) {
    if (!is_composite[i]) {
        primes.push_back(i);
    }
    for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
        is_composite[i * primes[j]] = true;
        if (i % primes[j] == 0) {
            break;
        }
    }
}

    2. 核心机制：为何 i % primes[j] == 0 时跳出循环？

    该条件是欧拉筛实现“每个合数仅被最小质因数筛除一次”的关键所在。我们通过以下分析揭示其数学本质：

    1. 设当前数为 i，当前素数为 p_j = primes[j]。
    2. 若 i % p_j == 0，说明 p_j 是 i 的一个质因数。
    3. 此时对于后续更大的素数 p_{j+1} > p_j，乘积 i * p_{j+1} 的最小质因数仍为 p_j（因为 i 已含 p_j）。
    4. 若继续执行，i * p_{j+1} 将被 p_{j+1} 筛去，但 p_{j+1} 并非其最小质因数，导致重复筛除。
    5. 因此，一旦 i % p_j == 0，立即跳出，确保每个合数只在其最小质因数作用下被标记。

    3. 数学归纳与实例验证

    iprimes[j]i * primes[j]i % primes[j]是否break说明
    4280是8 被 2 筛去，4 含因子 2，后续不再用更大素数筛
    52101否继续
    53152否继续
    62120是12 被 2 筛去，6 含 2，避免用 3 再筛 18（但 18 不在此步）
    72141否继续
    73211否
    75352否
    77490是7 是质数，49 被 7 筛去
    82160是8 含因子 2，不再用 3 等筛
    92181否继续

    4. 流程图展示执行逻辑

    graph TD A[开始] --> B{i从2到n} B --> C{is_composite[i]为false?} C -- 是 --> D[加入primes列表] C -- 否 --> E[j=0] D --> E E --> F{j < primes数量且i*primes[j] ≤ n?} F -- 是 --> G[标记i*primes[j]为合数] G --> H{i % primes[j] == 0?} H -- 是 --> I[break] H -- 否 --> J[j++] J --> F F -- 否 --> K[i++] I --> K K --> B B --> L[结束]

    5. 时间复杂度分析与去重保证

    欧拉筛的线性时间复杂度依赖于两个关键点：

    • 每个合数 x 只被访问一次，即当 i = x / p_min(x) 且 primes[j] = p_min(x) 时被筛去。
    • 由于 break 条件的存在，任何合数不会被其非最小质因数再次尝试筛除。
    • 内层循环对每个 i 的执行次数等于其不同质因数的个数，总和为 O(n)。
    • 该机制本质上是一种“责任分配”：每个合数由其最小质因数“负责”筛除，避免多头管理。
    • 这种设计思想在哈希表冲突解决、动态规划状态转移中也有类似体现。

    6. 常见误区与工程实践建议

    在实际编码中，开发者常犯以下错误：

    1. 忽略 i * primes[j] <= n 的边界检查，导致数组越界。
    2. 将 break 条件误写为 i % primes[j] != 0，破坏去重逻辑。
    3. 未初始化布尔数组，导致未定义行为。
    4. 在多线程环境下共享 primes 列表而未加同步，引发数据竞争。
    5. 对大范围筛法未使用位压缩技术，造成内存浪费。

    建议在生产环境中结合位图（BitSet）优化空间占用，并预估素数密度以合理分配内存。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

问题事件

  • 已采纳回答 12月11日
  • 创建了问题 12月10日