問題
1 から 100 までに素数はいくつあるでしょうか。50 から 60 まではどうでしょう。low ≤ p ≤ high を満たす素数 p の個数を数えてください。0 と 1 は素数ではないことに注意しましょう。high までのエラトステネスの篩を作れば、すぐに答えが出ます。
count_primes_in_range(low, high) を実装してください。
入力
low:区間の下限(この値を含みます)。
high:区間の上限(この値を含みます)。
出力
区間内の素数の個数を返してください。low > high のときは区間が空なので、答えは 0 です。
制約
0 ≤ low ≤ 1,000,000
0 ≤ high ≤ 1,000,000
例
入力:
low = 1
high = 100
期待される出力:
expected = 25
入力:
long long low = 1;
long long high = 100;
期待される出力:
long long expected = 25;
入力:
long low = 1;
long high = 100;
期待される出力:
long expected = 25;
解説
100 までの素数は 25 個(2, 3, 5, … 97)なので、答えは 25 です。
入力:
low = 50
high = 60
期待される出力:
expected = 2
入力:
long long low = 50;
long long high = 60;
期待される出力:
long long expected = 2;
入力:
long low = 50;
long high = 60;
期待される出力:
long expected = 2;
解説
50 から 60 の間の素数は 53 と 59 だけなので、答えは 2 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
high までの篩を作り、各素数の倍数をその2乗から消していきます。
ヒント 2
その後、low から high までで素数として残っている数を数えます。
ヒント 3
low が high より大きければ、何も計算する必要はありません。
目安の計算量
時間 O(high log log high)、追加メモリ O(high)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。