ウィキペディアから：
アルゴリズムの複雑さは
O(n(logn)(loglogn))ビット演算です。
どうやってそこにたどり着きますか？
複雑さにこのloglogn用語が含まれているということは、sqrt(n)どこかにあることを私に教えてくれます。
最初の100個の数値（n = 100）でふるいを実行していると仮定します。数値を複合としてマークするのに一定の時間がかかると仮定すると（配列の実装）、使用する回数は次のmark_composite()ようになります。
n/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n^2)
そして、次の素数を見つけるために（たとえば、7の倍数であるすべての数を取り消した後にジャンプするために5）、操作の数はになりますO(n)。
したがって、複雑さはになりますO(n^3)。同意しますか？
n/2 + n/3 + n/5 + … n/97 は O(n) ではありません。これは、項の数が一定ではないためです。[編集後の編集: O(n 2 ) は上限が緩すぎます。] 緩い上限は n(1+1/2+1/3+1/4+1/5+1/6+… 1/n) (n までのすべての数値の逆数の合計)、つまり O(n log n):調和数を参照してください。より適切な上限は n(1/2 + 1/3 + 1/5 + 1/7 + …) です。これは、n までの素数の逆数の合計であり、O(n log log n) です。（こちらまたはこちらをご覧ください。）
「次の素数を見つける」ビットは全体で O(n) のみであり、償却されます。ステップごとではなく、合計でn 回だけ次の数を見つけるために先に進みます。したがって、アルゴリズムのこの部分全体は O(n) しか取りません。
したがって、これら 2 つを使用すると、O(n log log n) + O(n) = O(n log log n) 算術演算の上限が得られます。ビット操作をカウントする場合、n までの数値を扱っているため、約 log n ビットがあり、log n の因数が入り、O(n log n log log n) ビット操作が得られます。
複雑さに loglogn 項が含まれているということは、どこかに sqrt(n) があることを示しています。
ふるい分け中に素数を見つけた場合P、現在の位置で数字を消し始めないことに注意してください + P; あなたは実際に で数字を消し始めますP^2。P以下のすべての倍数はP^2、以前の素数によって取り消されています。