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

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

思路

题目的意思是要求在

1

至

n

中选一些数，使得选取中的数两两互质，要最大化选取的个数。

要想要两两互质，那就应该选取质数，那问题就变成了求

1

至

n

中质数的个数。

但注意，

1

虽然不是质数，但它和任何数的最大公因数都是

1

，所以

1

也要算进去。

代码

CPP

#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;
}

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

文章操作

思路

代码

相关推荐

评论

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