题解 | 几乎是质数
几乎是质数
https://www.nowcoder.com/practice/bbcb0e0f5aad46f4920ee85c3ed5d34b
显然只需要将埃氏筛略加修改即可，开一个向量用来存放每一个数的质因子，质因子为零即为素数。
外层循环为素数，内层循环判断改素数为哪些数的质因子。
统计即可。
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
int main()
{
int n;cin>>n;
vector<vector<int>> ans(n+1);
int cnt=0;
for(int i=2;i<=n;i++)
{
if(ans[i].size()==0){
for(int j=2*i;j<=n;j+=i)
{
ans[j].push_back(i);
}
}
if(ans[i].size()==2){
cnt++;
}
}
cout<<cnt;
}
