数字选取--线性筛

题目描述:

给定正整数 ，现在有 $1,2,3, \dots , n $共计  $n$个整数。你需要从这 $n$个整数中选取⼀些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最⼤公因数为$1$ ）。请你最⼤化所选取整数的数量。
例如，当 $n=9$时，可以选择$1,5,7,8,9$ 共计$5$ 个整数。可以验证不存在数量更多的选取整数的⽅案。

输入格式:

⼀⾏，⼀个正整数 $n$，表⽰给定的正整数。

输出格式:

⼀⾏，⼀个正整数，表⽰所选取整数的最⼤数量。

数据范围:

对于 40% 的测试点，保证  $1\le n \le 1000$。
对于所有测试点，保证 $1\le n \le 10^6$ 。

样例输入:

(双击复制)

样例1：
6

样例2：
9

样例输出:

(双击复制)

样例1：
4

样例2：
5

时间限制: 1000ms
空间限制: 256MB

---

来源: gesp202509-5