题解：P14073 [GESP202509 五级] 数字选取

Yang_Jun · 2025-09-30 19:29:05 · 题解

这道题很简单的，反正我看到就秒了。

思路

题目的意思是要求在 1 至 n 中选一些数，使得选取中的数两两互质，要最大化选取的个数。

要想要两两互质，那就应该选取质数，那问题就变成了求 1 至 n 中质数的个数。

但注意， 1 虽然不是质数，但它和任何数的最大公因数都是 1，所以 1 也要算进去。

代码

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
    if(n==2||n==1) return true;//1本身不是质数，但为了简便，在判断质数时特判了1
    if(n%2==0) return false;
    for(int i=3;i*i<=n;i+=2){
        if(n%i==0) return false;
    }
    return true;
}
int main(){
    int n;
    cin>>n;
    int Prime=0;
    for(int i=1;i<=n;i++){
        if(isPrime(i)) Prime++;
    }
    cout<<Prime;
    return 0;
}