指定された上限未満の素数の合計

問題

素数とは、1より大きく、1と自分自身以外で割り切れない整数です。limit より小さいすべての素数を加算してください。limit 自体が素数であっても、合計には含めません。

prime_sum(limit) を実装してください。

limit: 排他的な上限値です。

条件を満たす素数の合計を返してください。該当する素数が存在しない場合は 0 を返してください。

0 ≤ limit ≤ 2,000,000。合計は符号付き64ビット整数で返してください。

例 1

入力：
limit = 12

期待される出力：
expected = 28

入力：
long long limit = 12;

期待される出力：
long long expected = 28;

入力：
long limit = 12;

期待される出力：
long expected = 28;

12 未満の素数は 2, 3, 5, 7, 11 です。これらの合計は 28 です。

例 2

入力：
limit = 2

期待される出力：
expected = 0

入力：
long long limit = 2;

期待される出力：
long long expected = 0;

入力：
long limit = 2;

期待される出力：
long expected = 0;

2 未満の素数は存在しません。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

主なコストは素数を効率よく見つけること。各数の素朴な割り算判定では遅すぎる。

ヒント 2

ふるいのように合成数を印付けし、未印のまま limit 未満の数を足し合わせる。

ヒント 3

limit 自身は素数でも含めないこと。小さい limit では 0 の場合もある。

目安の計算量

時間 O(limit log log limit)、追加メモリ O(limit)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。