分数: 350 点
问题陈述
正整数 当且仅当满足以下条件时, X 被称为好整数:
- 存在一对正整数 (a,b) 这样 X = 2^a \times b^2.
例如, 400 是一个很好的整数,因为 400 = 2^2 \times 10^2.
给定一个正整数 N,找到之间的好整数的数量 1 和 N,包括在内。
约束
- 1 \leq N \leq 10^{18}
- N 是一个整数。
输入
输入由标准输入按以下格式给出:
N
输出
打印之间的好整数的数量 1 和 N,包括在内。
示例输入 1
20
示例输出 1
5
之间有五个好整数 1 和 20: 2, 4, 8, 16,和 18.
因此,打印 5.
示例输入 2
400
示例输出 2
24
示例输入 3
1234567890
示例输出 3
42413
请注意,输入可能不适合 32- 位整数类型。