Responsive image

问题 3365 --奇偶数

3365: 奇偶数

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 13
[提交][状态][讨论版][命题人:]

题目描述

小劉这一天突发奇想，定义了一种新的奇偶数，他定义奇数为只有一个质因数的数（相同的质因数不被重复计算），定义偶数为质因数个数大于 1的数，1既不是奇数也不是偶数 ，现在小劉想求出1~n中的奇数个数，请你帮助他
例如：2=2为奇数，8=2*2*2为奇数，6=2*3为偶数

输入描述

一个整数n（1<=n<=5e6）

输出描述

输出奇数的个数

样例输入

5

样例输出

4

来源

23软3刘震峰 

[提交][状态]
ACM算法攻关部