description
给定 \(n\leq 10^{11}\) 求 1 到 \(n\) 中恰有 4 个因数的数的个数。
solution
这个数据范围容易想到筛子。
题目相当于让求 1 到 \(n\) 中可以表示成 \(p^3\) 或 \(p_1p_2\) (\(p,p_1,p_2\) 都是质数)的数的个数。
对于形如 \(p^3\) 的，直接枚举 \(p\)；
对于形如 \(p_1p_2\) 的，枚举 1 至 \(\sqrt{n}\) 内的质数，那么 \(p_1\) 和 \(p_2\) 中的较小的一个一定会被枚举到。假设枚举到了 \(p_0\)，它对答案的贡献就是 \(p+1\) 到 \(\lfloor\frac{n}{p}\rfloor\) 中质数的个数。然后就是 Min25 筛第一部分的板子了。
标签：CF665F,1p,题目,质数,个数,枚举 From： https://www.cnblogs.com/FreshOrange/p/17683395.html