质数计数
已关闭dadingPython / C++入场费 1 金币5 次提交
题目描述
给定一个整数 n，返回小于 n 的质数个数。
质数是大于1的自然数，除了1和它本身外没有其他因数。
例如：n=10，小于10的质数有2、3、5、7，共4个。 n=0或n=1时，结果为0。
输入格式
一个整数 n（0 ≤ n ≤ 5000000）
输出格式
一个整数，表示小于 n 的质数个数
输入输出样例
样例 1
输入：
10
输出：
4
样例 2
输入：
1
输出：
0
说明/提示
数据规模可达5×10^6，逐个判断O(n√n)会超时，考虑埃拉托斯特尼筛法（Sieve of Eratosthenes），时间O(n log log n)。