P14073 [GESP202509 五级] 数字选取

题目描述

给定正整数 $n$，现在有 $1,2,\dots ,n$ 共计 $n$ 个整数。你需要从这 $n$ 个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最大公因数为 $1$）。请你最大化所选取整数的数量。

例如，当 $n=9$ 时，可以选择 $1,5,7,8,9$ 共计 $5$ 个整数。可以验证不存在数量更多的选取整数的方案。

输入格式

一行，一个正整数 $n$，表示给定的正整数。

输出格式

一行，一个正整数，表示所选取整数的最大数量。

输入输出样例 #1

输入 #1

6

输出 #1

4

输入输出样例 #2

输入 #2

9

输出 #2

5

说明/提示

对于 $40\%$ 的测试点，保证 $1\le n\le 1000$。

对于所有测试点，保证 $1\le n\le 10^5$。

解析

取1到n范围内所有质数再加上1就可以了，使用埃氏筛或者欧拉筛都可以，详见代码：

埃氏筛

#include<bits/stdc++.h>
using namespace std;
int n;
bool a[100005];
int ans=1;
int main(){
    cin>>n;
    for(int i=2;i*i<=n;i++){
        if (a[i]==0){
            for(int j=i*i;j<=n;j+=i){
                a[j]=1;
            }
        }
    }
    for(int i=2;i<=n;i++){
        if (a[i]==0){
            ans++;
        }
    }
    cout<<ans;
	return 0;
}

欧拉筛

#include<bits/stdc++.h>
using namespace std;
int n, p[100005], cnt=0;
bool np[100005];
int main() {
    cin>>n;
    for (int i = 2; i <= n; i++) {
        if (np[i]==0) {
            cnt++;
            p[cnt] = i;
        }
        for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
            np[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
    cout<<cnt+1;
    return 0;
}