Namaran

Code daily. Without assist.

2026-11-19

spf_table.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> spf(16);
    for (int i = 2; i < 16; ++i)
        if (spf[i] == 0)
            for (int j = i * i; j < 16;
                 j += i)
                spf[j] = i;
    for (int x : {15, 12, 7})
        std::cout << spf[x] << ' ';
    std::cout << '\n';

これは何を出力するでしょうか?

Answer

Output

3 3 0 

外側のループは、spf[i] がまだ 0 の i だけを素数として扱い、その倍数に i を書き込みます。書き込む前に空いているかを確かめないので、1つの要素に何度も書き込まれ、最後に書いた値が残ります。内側のループは i * i から始まり、素数 i 自身には何も書きません。この3つの規則が同時に効くので、spf[x] に残るのは「2乗が x 以下になる x の素因数のうち最大のもの」で、そういう素因数がなければ 0 です。

このコードの値で確かめます。12 には、i = 2 のループが 4, 6, …, 12 と進んで 2 を書き、そのあと i = 3 のループが 9, 12, 15 と進んで 3 で上書きします。15 にも i = 3 のループが 3 を書きますが、15 のもう1つの素因数 5 のループは 25 から始まるので、16 未満には何も書きません。7 は偶数でも 3 の倍数でもなく、7 自身のループは 49 から始まるので、誰も書き込まずに 0 のまま残ります。こうして 3 3 0 が出ます。書き込みが重なっても、spf[i] == 0 で素数を見分ける判定は崩れません。合成数 i には2乗が i 以下の素因数が必ずあり、そのループが i に着く前に書き込んでいるからです。

表には最小の素因数が入ると思って読むと 3 2 0 になり、素数には自分自身が入ると思えば最後が 7 になります。上書きで最大の素因数が残ることには気付いても、内側のループが i * i から始まることを忘れると、15 に 5 が入ると考えて 5 3 0 と答えます。最小の素因数の表にするには、spf[j] == 0 のときだけ書き込み、素数 i には spf[i] = i と自分を入れます。