Namaran

Code daily. Without assist.

2026-08-25

is_prime_cached.c

#include <stdbool.h>

bool is_prime_slow(int n);

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

bool is_prime_cached(int n) {
    // write this: return is_prime_slow(n), but compute it only once per n;
    // a later call with the same n must reuse the cached result
}

0以上999以下のnについて、is_prime_cachedを実装してください。同じnで呼ばれたときはis_prime_slowを呼び直さず、前回の結果を再利用すること。

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

cache1本だけで「まだ計算していない」の番兵を兼ねようとすると、is_prime_slow(n)がfalseだった結果と衝突してしまいます(番兵を0にすると、falseという結果も0になるからです)。computedという別の配列で「計算済みかどうか」だけを管理すれば、番兵の値を選ぶ必要自体がなくなります。computedもcacheもstatic配列なので0(つまりfalse)埋めで初期化され、最初はどちらも「未計算」を正しく表せます。これは参考実装であり、唯一の正解ではありません。