数数
题号：NC266427
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛穿越到了异世界。

在异世界中，牛牛发现这里的人们对奇数和偶数有着独特的定义，在这里，奇数被定义为只有一个质因数的数（相同的质因数不被重复计算），偶数定义为质因数个数大于 1 的数，1 既不是奇数也不是偶数 。牛牛想要知道 1 ~ n 中偶数的个数，聪明的你能帮牛牛解决这个问题吗？

例如：2 = 2 ^ 1 是奇数，8 = 2 ^ 3 是奇数，45 = 3^2\times5 是偶数。

输入描述:

输入一个整数 n(1\leq n\leq 5*10^6)。

输出描述:

输出一个整数表示答案。
示例1

输入

复制 
5

输出

复制 
0
示例2

输入

复制 
6

输出

复制 
1