すべてのチャレンジ
簡単 0件解決済み 正答率0%

区間内の素数の個数

2つの境界の間(両端を含む)にある素数の個数を数えます。

このチャレンジで学べること

  • 篩で合成数に印を付けられる
  • 区間内の印の付いた値を数えられる
  • 空の区間と 0、1 を正しく扱える

問題

原文(英語)を表示

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

例

例 1
入力:
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 です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。