エラトステネスの篩（Sieve of Eratosthenes）の典型的な時間計算量はどれか？ 2025.09.22 エラトステネスの篩（Sieve of Eratosthenes）の典型的な時間計算量はどれか？ O(n^2) O(n) O(n log log n) O(n log n) エラトステネスの篩では小さい素数pについてその倍数を消す処理を行い、各整数kに対して1/ p の期待回数だけ処理が行われるため総和は n (1/2 + 1/3 + 1/5 + …) に近く、素数逆数和の漸近はlog log nに比例します。従って全体の時間計算量はO(n log log n)となります。 クイズタグ: 競技プログラミング関連記事 競技プログラミングクイズ！【問題 全10問・答え付き】 | 2025年09月版
