统计质数

Coddy 面试编程挑战：第五辑课程的第 3 课，共 3 课。

挑战

困难

编写一个函数 countPrimes，它接收一个整数 n，并返回小于 n 的质数个数。

注意：时间复杂度必须优于 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) {
    // 在这里编写代码
}

面试编程挑战：第五辑中的所有课

1挑战