Four Divisors
题目描述
F. Four Divisors
time limit per test
10 secondsmemory limit per test
768 megabytesinput
standard inputoutput
standard outputIf an integer a is divisible by another integer b, then b is called the divisor of a.
For example: 12 has positive 6 divisors. They are 1, 2, 3, 4, 6 and 12.
Let’s define a function D(n) − number of integers between 1 and n (inclusive) which has exactly four positive divisors.
Between 1 and 10 only the integers 6, 8 and 10 has exactly four positive divisors. So, D(10)=3.
You are given an integer n. You have to calculate D(n).
Input
The only line contains integer n (1≤n≤1011) − the parameter from the problem statement.
Output
Print the only integer c − the number of integers between 1 and n with exactly four divisors.
Examples
Input
10
Output
3
Input
20
Output
5
题目来源：fps-www.educg.net-codeforce-1-2833.xml.zip；FPS 共享题包，题包内第 743 题。保留原作者与原赛事署名。