题意概述

找到$1$~$n$中所有的偶数个数； 偶数定义为质因子个数大于1的数。

如何找到奇数

只要找打奇数就能求出偶数

我们已经知道在本题中奇数的定义是因子中只有一个质数，因此我们得知任意质素的k次幂都是奇数，我们只需要找到所有的奇数就能求出偶数个数。

所以只需要通过素数筛找到每一个素数，然后再找到小于等于$n$的最大次幂。

主要代码如下：

普通素数筛
  bool t[1e7];//bool调用时间比int快
  int ans = 0;//记录奇数个数
  for(int i = 2 ; i <= n ; i ++) { // 判断所有数
        if(!t[i]){ 
            ans ++ ;
            for(int j = i * i ; j <= n ; j *= i ) { // 找到剩余奇数
                ans ++;
            }
            //优化时间
            for(int j = i * i ; j <= n ; j += i) {
                t[j] = true;
            }
        }
    }

主要考察了同学对素数的理解和素数筛的运用

需要注意的是本题数据范围最大是 $1e7$，乘法运算时有可能会超 $int$ 范围，注意开 $longlong$