分数: 700 点
问题陈述
给你一个正整数 N。有一个空集 S,并且您可以执行任意多次以下操作:
- 选择任意正整数 x。对于每个 x, 2x,和 3x,将其添加到 S 如果尚未存在 S.
找出满足以下条件所需的最少操作数 \{1, 2, \dots, N\} \subseteq S.
约束
- 1 \leq N \leq 10^{9}
输入
输入由标准输入按以下格式给出:
N
输出
在一行中打印答案。
示例输入 1
7
示例输出 1
4
选择 1, 2, 5,和 7 产量 S = \{1, 2, 3, 4, 5, 6, 7, 10, 14, 15, 21\},满足条件。不可能用 3 次或更少的操作来满足该条件。
示例输入 2
25
示例输出 2
14