教科书级代码

数据有1e6
暴力肯定不行
标准解法（无邪修）
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n;
bool pis[MAXN];
bool biaoji[MAXN];
typedef long long ll;
void f ( int x ) {
for (int i = 2;i <= x; i++){
pis[i]=1;
}
for(int i=2;i<=x;i++){
if(pis[i]){
for(ll j=1LLii;j<=x;j += i){
pis[j]=0;
}
}
}
}
int MAX_PIS=MAXN;
int ans=0;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
f(MAX_PIS);
cin >> n;
for (int i = 1; i <= n ; i++) {
int x;
cin>>x;
if(pis[x]){
if(!biaoji[x]){
biaoji[x]=1;
ans++;
}
continue;
}
for(int j=2;1LLjj<=x;j++){
if(x%j == 0){
if(pis[j] && !biaoji[j]){
biaoji[j]=1;
ans++;
}
while(x%j == 0){
x /= j;
}
}
}
if(x>1){
if(!biaoji[x]){
biaoji[x]=1;
ans++;
}
}
}
cout<<ans;
return 0;
}