题目传送门 目前还不知道，题目还未加入洛谷题库
题目概述
T1：
给定一个数 \(n(n \le 10^5)\)，你需要选出若干个在1到 \(n\) 范围内的数，使其中任意两个数互质（即两数最大公因数为1），问最多你能选几个数？
解题思路
我们可以先使用贪心的思路去思考
假设 \(n=10\)，我们从1开始选数
- 首先，选上1，因为所有整数和1都互质，所以一定要选择
- 接着，考虑2，发现可以选择，那么就选择
- 接着3，也可以选择，选择
- 接着4，发现它和2不互质，不选
- 5，选
- 6和2/3不互质
- 7，选
- 8，和2不互质
- 9，和3不互质
- 10，和2/5不互质
我们发现，我么选出来的数是 \({1,2,3,5,7}\)，这已经是数量最多的了
这时候我们发现规律，最优情况下，我们选出来的数都是 1 或者 \(n\) 以内的素数（即只有合数不选）
所以思路就很明确了，把 1 和所有素数选择，那么答案就是 \(n\) 以内的素数\(+1\)
所以我们可以把 \([1,n]\) 区间的素数筛出来，用素数的个数 \(+1\) 即可
Code
我的代码选择使用欧拉筛来筛素数
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
bool vis[100005]; // 标记是否是素数
int a[100005]; // 存放素数
int cnt; // 素数个数
signed main()
{cin >> n; // 输入nfor (int i = 2; i <= n; i++){if (!vis[i]){// 如果i是素数，则将其存入数组a中cnt++; // 素数个数加1a[cnt] = i; // 存入数组a中}for (int j = 1; j <= cnt && i * a[j] <= n /*防止溢出*/; j++){// 枚举数组a中的素数，如果i能整除a[j]，则说明i不是素数，跳出循环vis[i * a[j]] = true; // 将i*a[j]标记为非素数if (i % a[j] == 0) // 如果i能整除a[j]，则说明i不是素数，跳出循环{break;}}}cout << cnt + 1 << endl; // 输出素数个数+1(因为1不是合数)return 0;
}