2026-11-19
sieve.cpp
#include <iostream>
#include <vector>
int main() {
const int n = 100'000;
std::vector<int> spf(n + 1);
for (int i = 2; i <= n; ++i) {
if (spf[i] != 0)
continue;
spf[i] = i;
for (int j = i * i; j <= n; j += i)
if (spf[j] == 0)
spf[j] = i;
}
for (int x = 99'990; x > 1; x /= spf[x])
std::cout << spf[x] << ' ';
std::cout << '\n';
}
10万までの各整数について、それを割り切る最小の素数を spf に入れ、その表を引いて 99990 を素因数分解するプログラムです。2 3 3 5 11 101 と1行出るはずが、いまは何も出ないまま Segmentation fault で落ちます。
Answer
Wrong
spf[i] = i;
for (int j = i * i; j <= n; j += i)
if (spf[j] == 0)
spf[j] = i;
i * i は int どうしの掛け算なので、結果も int です。32ビットの int の最大値は 2147483647 で、46340 の2乗 2147395600 までは収まりますが、46341 の2乗 2147488281 は収まりません。n が 10万なので、外側のループは 46341 以上の素数にも届き、そこで符号付き整数のオーバーフローという未定義動作が起きます。このプログラムでは掛け算の結果が負の数に折り返されたらしく、j <= n が真になって spf[j] が配列の外を読み書きし、出力を始める前に落ちています。
Right
spf[i] = i;
for (long long j = 1LL * i * i;
j <= n;
j += i)
if (spf[j] == 0)
spf[j] = i;
1LL * i で片方を先に long long にすると、掛け算そのものが long long で行われます。10万の2乗は 1010 で long long に十分収まるので、i * i が n を超える素数では内側のループが1回も回らずに終わります。i * i から始めてよいのは、i より小さい素因数を持つ倍数には、その素数のループがすでに書き込んでいるからです。1
- 小さい
nで試すと、i * iが溢れる前に外側のループが終わるので、この欠陥は表に出ません。-fsanitize=undefinedを付けてビルドすると、溢れた掛け算の行を指して実行時に報告されます。