204. 计数质数
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
提示：
0 <= n <= 5 * 106
解析：
素数筛板子，不要打表，直接求到n即可
class Solution {
public:
int vis[5000010];
int prime[5000010];
int phi[5000010];
int ans;
int init_prime(int n)
{
ans = 0;
int ret = 0;
memset(vis, 0, sizeof(vis));
for(int i = 2; i < n; i++)
{
if(vis[i] == 0)
{
prime[ans++] = i;
for(long long j = (long long)i * i; j < n; j += i)
vis[j] = 1;
}
ret += 1 - vis[i];
}
return ret;
}
int countPrimes(int n) {
return init_prime(n);
}
};
标签：prime,204,vis,int,质数,示例,long,计数 From： https://www.cnblogs.com/WTSRUVF/p/16760037.html