C++怎么使用欧拉线性筛法求素数-C++-PHP中文网

欧拉筛确保每个合数仅被其最小质因子筛一次；通过if(i%primes[j]==0)及时break，避免重复筛，实现线性时间复杂度。

c++怎么使用欧拉线性筛法求素数

欧拉筛的核心逻辑：每个合数只被最小质因子筛一次

欧拉筛（线性筛）不是靠“标记倍数”来筛，而是用已知质数去生成新合数，并强制要求：只用当前数的最小质因子去筛。关键在于 if (i % primes[j] == 0) 这个判断——一旦成立，立刻 break，防止用更大的质数重复筛同一个合数。

比如筛到 i = 12 时，primes = [2,3,5,...]，先用 2 筛出 12 * 2 = 24；接着用 3，发现 12 % 3 == 0，说明 3 是 12 的最小质因子（因为 12 = 2²×3），再往后用 5 筛 12×5=60 就不对了——60 的最小质因子是 2，它早该在 i=30 时被 2 筛掉。所以必须在此中断。

标准实现模板与关键变量含义

以下是最常用、无冗余的 C++ 实现（std::vector 版本），注意三个核心变量的作用：

std::vector<int> primes;
std::vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <ul>
<li>
<code>primes</code>：只存质数，顺序即筛出顺序，后续可直接用于质因数分解等</li>
<li>
<code>is_prime[i]</code>：布尔数组，下标即数字，<code>true</code> 表示尚未被筛，最终为质数</li>
<li><code>i * primes[j] ：防止越界，这是循环终止条件之一，不能省略</code></li>
</ul>
<h3>常见错误：break 位置错、越界、初始化遗漏</h3>
<p>这三个地方写错，筛出来的就不是线性复杂度，甚至结果错误：</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
														src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
													<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
												</div>
												<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>
<ul>
<li>把 <code>break</code> 写在 <code>if</code> 外面，或漏掉 <code>break</code> → 同一个合数被多次标记，退化成埃氏筛，时间变 <code>O(n log log n)</code>
</li>
<li>
<code>i * primes[j]</code> 没判 n 接近 <code>INT_MAX</code> 时）</li>
<li>忘记设 <code>is_prime[0] = is_prime[1] = false</code> → <code>0</code> 和 <code>1</code> 被误认为质数</li>
<li>用 <code>int i = 1</code> 开始循环 → <code>1 % primes[0]</code> 永远不为 0，但 <code>1</code> 不是质数，且 <code>1 * primes[j]</code> 会把所有质数本身标为合数</li>
</ul>
<h3>筛完后怎么快速查某个数是不是素数？</h3>
<p>筛完后，<code>is_prime[x]</code> 就是 <code>O(1)</code> 查询答案，前提是 <code>x  且已分配足够空间。不要在筛完后再遍历 <code>primes</code> 去二分查找——那是浪费已有的布尔表。</code></p>
<p>如果只需要质数列表而不需要单点查询，可以省掉 <code>is_prime</code> 数组，只维护 <code>primes</code>，并在内层循环中用 <code>primes[j]  替代 <code>i % primes[j] == 0</code> 的判断逻辑（本质相同，但更难理解）。不过绝大多数场景建议保留 <code>is_prime</code>，清晰且复用性强。</code></p>
<p>边界值容易被忽略：当 <code>n  时，<code>primes</code> 为空，<code>is_prime</code> 数组长度应为 <code>n+1</code>（哪怕 <code>n=0</code>），否则 <code>is_prime[0]</code> 访问越界。</code></p></bool></int>

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！