Namaran

Code daily. Without assist.

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

  1. 小さい n で試すと、i * i が溢れる前に外側のループが終わるので、この欠陥は表に出ません。-fsanitize=undefined を付けてビルドすると、溢れた掛け算の行を指して実行時に報告されます。