题解 | 几乎是质数

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{
	int n,cnt=0;//可以找出每一个数有几个质因数 方法如下 可以使用set记录个数 超过2就直接break
	cin >> n;//不过这样很慢 建议去学一下筛法
	for(int i=2;i<=n;i++)
	{
		set<int>s;
		int temp=i;
		for(int j=2;j*j<=i;j++)
		{
			if(temp%j==0) s.insert(j);
			while(temp%j==0)
			{
				temp/=j;
			}
			if(s.size()>2) break; 
		}
		if((s.size()==2&&temp==1)||(s.size()==1&&temp>1)) cnt++;
	}
	cout << cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}