筛质数zz

给定一个正整数 nn，请你求出 1∼n1∼n 中质数的个数。

输入格式

共一行，包含整数 nn。

输出格式

共一行，包含一个整数，表示 1∼n1∼n 中质数的个数。

数据范围

1≤n≤1061≤n≤106

输入样例：

8

输出样例：

4

#include <iostream>
using namespace std;
const int N=1e6+10;
int cnt;
bool st[N];
int primes[N];
void get_primes(int n)
{for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i;for(int j=i+i;j<=n;j+=i)    st[j]=true;}}
}
int main()
{int n;cin>>n;get_primes(n);cout<<cnt<<endl;// for(int i=0;i<cnt;i++)// {//     cout<<primes[i]<<endl;// }
}

#include <iostream>
using namespace std;
const int N=1e6+10;
int cnt;
bool st[N];
int primes[N];
void get_primes(int n)
{for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i;}for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i]=true;if(i%primes[j]==0)  break;}}
}
int main()
{int n;cin>>n;get_primes(n);cout<<cnt<<endl;// for(int i=0;i<cnt;i++)// {//     cout<<primes[i]<<endl;// }
}