在 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; ii<=n; i++){ if(isprime[i]==false){ for(int j=i; ij<=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; }