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

Zzq627 · 2025-09-30 20:46:50 · 题解

思路：这道题的意思就是选出1到n区间内两两互质最多的数，类似埃氏筛找到一个数再把它的所有倍数筛掉即可

### 五级太水了~~~~

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,n1[100000]={0},sum=0;
    cin>>a;
    for(int i = 2;i<=a;i++){
        if(n1[i]==0){
            for(int j = 2*i;j<=a;j+=i){
                n1[j] = 1;
            }
        }
    }
    for(int i = 1;i<=a;i++){
        if(n1[i]!=1)sum++;
    }
    cout<<sum;
}