题解 | 几乎是质数

显然只需要将埃氏筛略加修改即可，开一个向量用来存放每一个数的质因子，质因子为零即为素数。
外层循环为素数，内层循环判断改素数为哪些数的质因子。
统计即可。
#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;
}