Namaran

Code daily. Without assist.

2026-08-25

is_prime_cached.c

#include <stdbool.h>

bool is_prime_slow(int n);

static int cache[1000];

bool is_prime_cached(int n) {
    if (cache[n] != 0)
        return cache[n] == 1;
    bool result = is_prime_slow(n);
    cache[n] = result ? 1 : 0;
    return result;
}

is_prime_cachedは同じnについてis_prime_slowを1回だけ呼ぶつもりですが、nが素数でないときは毎回呼び直してしまいます。何が問題で、どう直せばよいでしょうか?

Answer

cache[n]の初期値である0を「まだ計算していない」の番兵として使っていますが、is_prime_slow(n)がfalseだったときの結果も同じ0として保存してしまいます。番兵と「計算済みでfalseだった」を区別できないので、素数でないnを尋ねるたびに毎回is_prime_slowを呼び直してしまいます(素数の方は1が保存され番兵と衝突しないので、2回目以降はちゃんとキャッシュが効きます)。1本の配列に番兵を混ぜるのではなく、「計算済みかどうか」を別の配列で管理すれば直ります: 

static bool computed[1000];
static bool cache[1000];

bool is_prime_cached(int n) {
    if (!computed[n]) {
        cache[n] = is_prime_slow(n);
        computed[n] = true;
    }
    return cache[n];
}