自动搬运

查看原文

来自洛谷，原作者为

	Little_x_starTYJ 愿时光能缓，愿故人不散！ || 众所周知，如果把灯泡放在嘴里，即使你自己一个人也取得出来灯泡。

搬运于2025-08-24 21:16:16，当前版本为作者最后更新于2024-04-29 15:31:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

这道题目的数据范围有点大，暴力算法的时间复杂度是 $O(n^2)$ 的，明显超时，于是我们可以先预处理出 $1\sim n$ 的所有数的最大质因子。但是暴力找到最大质因子也是很慢的，所以我们可以先筛出每个数的最大质因子，最后统计一下即可。

为什么可以用筛法呢？因为例如数字 $6$，他的质因子有 $2$ 和 $3$，于是它在 $i = 2$ 时被处理了一次。当 $i = 3$ 时，由于他是 $3$ 的倍数，所以它又被处理了一次，最后我们算出它的最大质因子为 $3$。

注意：虽然 $1$ 没有质因子，但是也要算入答案。

CODE:

#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int ans;
int main() {
	int n, b;
	cin >> n >> b;
	a[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!a[i]) {
			for (int j = i; j <= n; j += i)
				a[j] = i;
		}
	}
	for (int i = 1; i <= n; i++) { 
		if (a[i] <= b)
			ans++;
	}
	cout << ans;
	return 0;
}