D - AABCC
Editorial
/


Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 以下の正整数のうち、 a<b<c なる 素数 a,b,c を用いて a^2 \times b \times c^2 と表せるものはいくつありますか?
制約
- N は 300 \le N \le 10^{12} を満たす整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
1000
出力例 1
3
1000 以下で条件を満たす整数は以下の 3 つです。
- 300 = 2^2 \times 3 \times 5^2
- 588 = 2^2 \times 3 \times 7^2
- 980 = 2^2 \times 5 \times 7^2
入力例 2
1000000000000
出力例 2
2817785
Score : 400 points
Problem Statement
How many positive integers no greater than N can be represented as a^2 \times b \times c^2 with three primes a,b, and c such that a<b<c?
Constraints
- N is an integer satisfying 300 \le N \le 10^{12}.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
1000
Sample Output 1
3
The conforming integers no greater than 1000 are the following three.
- 300 = 2^2 \times 3 \times 5^2
- 588 = 2^2 \times 3 \times 7^2
- 980 = 2^2 \times 5 \times 7^2
Sample Input 2
1000000000000
Sample Output 2
2817785