给定一个正整数n,请你求出1~n中质数的个数。
输入格式
共一行,包含整数n。
输出格式
共一行,包含一个整数,表示1~n中质数的个数。
数据范围
1≤n≤106
输入样例:
8
输出样例:
4
线性筛法:保证了每个合数都会被他的最小质因子筛去
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll primes[N];
bool st[N];
ll cnt;
ll get_primes(ll n)
{
for(ll i=2;i<=n;i++) //每个数都要判断是否是质数;
{
if(!st[i])primes[cnt++]=i; //没有被筛过说明时质数;
for(ll j=0;primes[j]<=n/i;j++) //筛掉大于n的合数无意义;
{
st[primes[j]*i]=true; //这两步保证了每个合数都会被他的最小质因子筛去
//如20会在i=10,primes[j]为2时筛去,
// 15会在i=5,primes[j]为3时筛去;
if(i%primes[j]==0)break; //如i=6时,primes[j]=2时应该跳出;
//如果不跳出,primes[j+1]=3,将18筛去,
//但18应该在i=9时被2筛去,就不能保证个合数
//都会被他的最小质因子筛去;
}
}
}
int main()
{
ll n;
cin>>n;
get_primes(n);
cout<<cnt;
}
//埃法筛素数o(lnlnn);
#include<iostream>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll primes[N],cnt;
bool st[N];
ll get_primes(ll n)
{
for(ll i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=n;
for(ll j=i+i;j<=n;j+=i)st[j]=true; //每次去掉是素数的数的倍数;
}
}
}
int main()
{
ll n;cin>>n;
get_primes(n);
cout<<cnt<<endl;
}