エラトステネスの篩の計算量蟻本には、エラトステネスの篩の計算量はO(n log log n) と書いてあります。 log log nってなんぞや？どこから出てきたの？とずっと疑問でしたが、何故こうなるか分かったのでメモしておきます。 C++で書く場合は、概ね以下のようなコードが一般的かと思います。 bool isPrime[N]; int main() { for (int i = 2; i < N; i++) isPrime[i] = true; for (int i = 2; i < N; i++) { if (!isPrime[i]) continue; for (int j = 2 * i; j < N; j += i) isPrime[j] = false; } } まず簡単のため、上のソースの”素数でないなら飛ばす”という処理（※）が無かった場合を考えてみます。 （※）if (!isPrime[i] .
