5378 - 数字选取
题目描述
给定正整数 n，现在有 1，2，……，n 共计 n 个整数。你需要从这 n 个整数中选取些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最公因数为 1 ）。请你最大化所选取整数的数量。
例如，当 n=9 时，可以选择 1,5,7,8,9 共计 5 个整数。可以验证不存在数量更多的选取整数的案。
输入
一行，一个正整数 n ，表示给定的正整数。
输出
一行，一个正整数，表示所选取整数的最大数量。
样例
输入
6
输出
4
输入
9
输出
5
说明
数据范围
对于 40 \% 的测试点，保证 1 \le n \le 1000 。 对于所有测试点，保证 1 \le n \le 10^5 。
来源
GESP 2025年09月认证 C++5级真题
标签
