找全部质数即可

在 1,2,…,n 共计 n 个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质，最大化所选取整数的数量。

可以证明，只选取 质数和 1 可以满足要求。

对于任意一个质数 p，它所有的倍数都不可选，所以最多只能选其中一个，而选某个合数有可能造成两个及以上质数不可选，所有选质数才能最大化所选取整数的数量。
然后 1 也是可以选的，因为 1 和别的数的最大公因数也为 1。
所以最终的策略就是质数个数加一。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
bool isprime[N];
void aishuai(int n){
	isprime[0]=isprime[1]=true;
	for(int i=2; i*i<=n; i++){
		if(isprime[i]==false){ 
			for(int j=i; i*j<=n; j++){
				isprime[i*j]=true; 
			}
		}
	}
}
int main() {
	int n, cnt=0;
	cin>>n;
	aishuai(n);
    for(int i=2; i<=n; i++){
        if(isprime[i]==false) cnt++;
    }
	cout<<cnt+1;
	return 0;
}