题目描述
给定一个正整数n,请你求出1~n中质数的个数。
输入格式
共一行,包含整数n。
输出格式
共一行,包含一个整数,表示1~n中质数的个数。
数据范围
1≤n≤106
样例
1.
输入样例:
8
输出样例:
4
2.
输入样例:
10
输出样例:
4
算法1
(线性筛素数)
一看数据范围如果暴力就 TLE
所以我们来个 “线性筛素数”;
void GetPrime(int n)
{
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = 0;
for(int i = 2; i <= n; i++)
{
if(isPrime[i])
Prime[++cnt] = i;
for(int j = 1; j <= cnt && i*Prime[j] <= n; j++)
{
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0)
break;
}
}
}
参考文献
C++ 代码
#include <cstdio>
#include <cstring>
bool isPrime[100000010];
int Prime[6000010], cnt = 0;
int ans=0;
void GetPrime(int n)
{
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = 0;
for(int i = 2; i <= n; i++)
{
if(isPrime[i])
Prime[++cnt] = i;
for(int j = 1; j <= cnt && i*Prime[j] <= n; j++)
{
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0)
break;
}
}
}
int main()
{
int n;
scanf("%d", &n);
GetPrime(n);
printf("%d",cnt);
return 0;
}