欧拉筛笔记

核心原理

欧拉筛通过‌最小质因子筛除法‌确保每个合数仅被标记一次，实现O(n)时间复杂度

其核心逻辑是：

遍历时动态维护质数表primes[] 用当前数i与质数表内各质数p相乘标记合数ip 当i%p==0时终止内层循环，避免重复标记（如12=34和12=2*6）

算法实现步骤

初始化‌：

布尔数组isPrime[]标记素数状态（初始全为true） 动态数组primes[]存储筛出的素数

双重循环‌：

外层遍历2~n，若isPrime[i]==true则存入primes[] 内层用当前i与primes[]中各质数相乘，标记合数i*primes[j] 关键优化：当i%primes[j]==0时跳出内层循环

终止条件‌：

当i*primes[j] > n时停止内层循环 最终primes[]即为所有≤n的素数

‌功能‌： 输出≤n的所有素数，如输入100输出2 3 5 7...97

‌特点‌： 线性时间复杂度O(n)，空间复杂度O(n)

‌优化点‌： i%primes[j]==0时终止内层循环

适用场景 大范围素数筛选 小范围简单场景 注意事项 ‌数组越界‌：内层循环需判断i*primes[j] <= n ‌类型选择‌：大范围时建议使用long long防溢出 ‌性能优化‌：可预先分配primes[]内存（如`res