https://www.33dai.wiki/index.php?action=history&feed=atom&title=06-%E6%95%B0%E5%AD%A6%E7%9B%B8%E5%85%B3%2F01-%E8%B4%A8%E6%95%B0%E5%88%A4%E6%96%AD%E4%B8%8E%E7%AD%9B%E6%B3%95
06-数学相关/01-质数判断与筛法 - 版本历史
2026-05-20T23:10:02Z
本wiki上该页面的版本历史
MediaWiki 1.45.1
https://www.33dai.wiki/index.php?title=06-%E6%95%B0%E5%AD%A6%E7%9B%B8%E5%85%B3/01-%E8%B4%A8%E6%95%B0%E5%88%A4%E6%96%AD%E4%B8%8E%E7%AD%9B%E6%B3%95&diff=361&oldid=prev
33DAI：导入1个版本
2026-05-20T18:12:11Z
<p>导入1个版本</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="zh-Hans-CN">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">←上一版本</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2026年5月20日 (三) 18:12的版本</td>
</tr><tr><td colspan="4" class="diff-notice" lang="zh-Hans-CN"><div class="mw-diff-empty">（没有差异）</div>
</td></tr>
<!-- diff cache key my_wiki:diff:1.41:old-360:rev-361 -->
</table>
33DAI
https://www.33dai.wiki/index.php?title=06-%E6%95%B0%E5%AD%A6%E7%9B%B8%E5%85%B3/01-%E8%B4%A8%E6%95%B0%E5%88%A4%E6%96%AD%E4%B8%8E%E7%AD%9B%E6%B3%95&diff=360&oldid=prev
->Importer：批量导入三三文档
2026-05-20T16:50:33Z
<p>批量导入三三文档</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<tr class="diff-title" lang="zh-Hans-CN">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">←上一版本</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2026年5月20日 (三) 16:50的版本</td>
</tr><tr><td colspan="2" class="diff-notice" lang="zh-Hans-CN"><div class="mw-diff-empty">（没有差异）</div>
</td></tr></table>
->Importer
https://www.33dai.wiki/index.php?title=06-%E6%95%B0%E5%AD%A6%E7%9B%B8%E5%85%B3/01-%E8%B4%A8%E6%95%B0%E5%88%A4%E6%96%AD%E4%B8%8E%E7%AD%9B%E6%B3%95&diff=261&oldid=prev
33DAI：导入1个版本
2026-05-20T16:25:37Z
<p>导入1个版本</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<tr class="diff-title" lang="zh-Hans-CN">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">←上一版本</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2026年5月20日 (三) 16:25的版本</td>
</tr><tr><td colspan="2" class="diff-notice" lang="zh-Hans-CN"><div class="mw-diff-empty">（没有差异）</div>
</td></tr></table>
33DAI
https://www.33dai.wiki/index.php?title=06-%E6%95%B0%E5%AD%A6%E7%9B%B8%E5%85%B3/01-%E8%B4%A8%E6%95%B0%E5%88%A4%E6%96%AD%E4%B8%8E%E7%AD%9B%E6%B3%95&diff=260&oldid=prev
->Importer：批量导入三三文档
2026-05-20T16:22:29Z
<p>批量导入三三文档</p>
<p><b>新页面</b></p><div><br />
== 判断单个质数 ==<br />
<br />
<math>O(\sqrt{x})</math><br />
<br />
<syntaxhighlight lang="cpp"><br />
bool is_prime(long long x)<br />
{<br />
if (x < 2)<br />
return false;<br />
for (long long i = 2; i * i <= x; i++)<br />
if (x % i == 0)<br />
return false;<br />
return true;<br />
}<br />
</syntaxhighlight><br />
<br />
== 埃氏筛 ==<br />
<br />
<math>O(n\log \log n)</math><br />
<br />
<syntaxhighlight lang="cpp"><br />
const int MAXN = 10'000'000;<br />
bool p[MAXN + 1];<br />
<br />
// 筛出 1~n 中的每个数是否为质数<br />
void get_primes(int n)<br />
{<br />
p[0] = p[1] = false;<br />
for (int i = 2; i <= n; i++)<br />
p[i] = true;<br />
for (int i = 2; i <= n; i++)<br />
if (p[i])<br />
for (int j = i + i; j <= n; j += i)<br />
p[j] = false;<br />
}<br />
</syntaxhighlight><br />
<br />
== 线性筛（欧拉筛） ==<br />
<br />
<math>O(n)</math>。每个合数只被其最小质因子筛去。<br />
<br />
<syntaxhighlight lang="cpp"><br />
const int MAXN = 10'000'000;<br />
bool p[MAXN + 1];<br />
vector<int> pri;<br />
<br />
void get_primes(int n)<br />
{<br />
for (int i = 1; i <= n; i++)<br />
p[i] = true;<br />
p[0] = p[1] = false;<br />
for (int i = 2; i <= n; i++)<br />
{<br />
if (p[i])<br />
pri.push_back(i);<br />
for (int j = 0; j < pri.size(); j++)<br />
{<br />
if (1LL * i * pri[j] > n)<br />
break;<br />
p[i * pri[j]] = false;<br />
if (i % pri[j] == 0)<br />
break;<br />
}<br />
}<br />
}<br />
</syntaxhighlight><br />
<br />
核心原理：对于每个数 <math>i</math>，用已求出的质数 <math>pri[j]</math> 筛去 <math>i \times pri[j]</math>。当 <math>i</math> 是 <math>pri[j]</math> 的倍数时停止，保证每个合数只被最小质因子筛去。<br />
<br />
== 质因数分解 ==<br />
<br />
<syntaxhighlight lang="cpp"><br />
// 对 x 进行质因数分解，结果存储在 pairs<质因子, 次数> 中<br />
vector<pair<long long, int>> factor(long long x)<br />
{<br />
vector<pair<long long, int>> res;<br />
for (long long i = 2; i * i <= x; i++)<br />
if (x % i == 0)<br />
{<br />
int cnt = 0;<br />
while (x % i == 0)<br />
x /= i, cnt++;<br />
res.push_back({i, cnt});<br />
}<br />
if (x > 1)<br />
res.push_back({x, 1});<br />
return res;<br />
}<br />
</syntaxhighlight><br />
<br />
<br />
[[Category:数学相关]]<br />
[[Category:三三文档]]</div>
->Importer