题目描述
给定一个正整数 n,请你求出 1∼n 中质数的个数。
输入格式
共一行,包含整数 n。
输出格式
共一行,包含一个整数,表示 1∼n 中质数的个数。
数据范围
1≤n≤106
输入样例:
8
输出样例:
4
代码
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e6 + 10;
int prime[N];
bool st[N];
//朴素筛
int getPrimes1(int n)
{
int cnt = 0;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) prime[cnt ++ ] = i;
for (int j = 2 * i; j <= n; j += i)
{
st[j] = true;
}
}
return cnt;
}
//埃式筛法
int getPrimes2(int n)
{
int cnt = 0;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
prime[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
{
st[j] = true;
}
}
}
return cnt;
}
//线性筛
int getPrimes3(int n)
{
int cnt = 0;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) prime[cnt ++ ] = i;
for (int j = 0; prime[j] <= n / i; j ++ )
{
st[prime[j] * i] = true;
if (i % prime[j] == 0) break; // 控制循环,无重复筛选,保持用最小质因数筛,例10 被2筛掉了,5无需再筛
}
}
return cnt;
}
// 线性筛(有重复)
int getPrimes4(int n)
{
int cnt = 0;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) prime[cnt ++ ] = i;
for (int j = 0; j < cnt && prime[j] * i <= n; j ++ ) //prime[j] * i <= n 超过n 的合数无需再筛
// j < cnt 用已经得到的素数往后筛i倍数的合数(有重复)
{
st[prime[j] * i] = true;
}
}
return cnt;
}
int main()
{
int n;
cin >> n;
cout << getPrimes2(n) << endl;
return 0;
}