Count Primes
Coddyの「コーディング面接チャレンジ - パック V」コースのレッスン 3/3。
チャレンジ
難しい整数 n を受け取り、n 未満の素数の数を返す関数 countPrimes を作成してください。
注意: 時間計算量は O(nlogn) より効率的である必要があります。
1 <= n <= 1000000
例:
入力 - 10
期待される出力 - 4
解説 - 10 未満の素数は 4 つあります: 2, 3, 5, 7
入力 - 13
期待される出力 - 5
解説 - 13 未満の素数は 5 つあります: 2, 3, 5, 7, 11 - 13 は含まれないことに注意してください！
自分で試してみよう
int countPrimes(int n) {
// ここにコードを記述してください
}