显然只有两种情况： p1* p2 或者 p1^3(p1,p2为质数）。所以可以先打个质数表（用埃氏筛就够了），然后枚举p1算算有多少个p2 满足 p1* p2<=n（二分或者双指针都可以）。

当然如果你记得唯一分解定理，那么也可以直接快速求出来每个数的因子个数，搭配欧拉筛甚至能做到 O(n) 处理出来 1~n每个数的因子个数，就更简单了。