#G1132. [GESP202509 五级] 数字选取

[GESP202509 五级] 数字选取

[GESP202509 五级] 数字选取

题目描述

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

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

输入格式

一行,一个正整数 nn,表示给定的正整数。

输出格式

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

样例 #1

样例输入 #1

6

样例输出 #1

4

样例 #2

样例输入 #2

9

样例输出 #2

5

数据范围

测试点占比 约束
40% 1≤n≤10001 \le n \le 1000
100% 1≤n≤1051 \le n \le 10^5