AcWing 868. 筛质数
原题链接
简单
作者:
minux
,
2020-04-28 15:44:55
,
所有人可见
,
阅读 455
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int PRIME[N];
bool vis[N];
int n;
int cnt;
void getPrimes(int n){
for(int i=2; i<=n; ++i){
// 埃氏筛
// if(!vis[i]) PRIME[cnt++]=n;
// for(int j=i+i; j<=n; j+=i) vis[j]=true;
// 线性筛法
if(!vis[i]) PRIME[cnt++]=i;
for(int j=0; PRIME[j]<=n/i; ++j){
vis[PRIME[j]*i]=true;
if(i%PRIME[j]==0) break; // 满足条件时: PRIME[j]是i的最小质因子
}
}
}
int main(){
// 质数筛
memset(PRIME, 0x00, sizeof PRIME);
memset(vis, 0x00, sizeof vis);
cin>>n;
cnt=0;
getPrimes(n);
cout<<cnt<<endl;
return 0;
}