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

· · 题解

P14073 [GESP202509 五级] 数字选取

题外话

这题真的能到橙吗……

思路

因为要使得所选取的整数中任意两个不同的整数均互质，所以……找出 1 \sim n的素数就行啦~~~

Ac code

#include<bits/stdc++.h>
using namespace std;
bool Isprime(int x)
{
    if(x<=1)return 0;
    if(x==2)return 1;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)return 0;
    return 1;
}
int main()
{
    int n,sum=1;
    cin>>n;
    for(int i=2;i<=n;i++)
        if(Isprime(i))sum++;
    cout<<sum<<endl;
    return 0;
}