洛谷 B3969 [GESP202403 五级] B-smooth 数题解

本文主要是介绍洛谷 B3969 [GESP202403 五级] B-smooth 数题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

我们只要求出每个数的最大质因数，再一个个判断是否满足要求即可。

如何找到每个数的最大质因数呢？其实，我们可以在埃氏筛法的基础上进行改进，从而达到算出最大质因数的目的。

让我们先来了解一下埃氏筛法，知道的人可以跳过。埃氏筛法，首先定义一个 bool 型数组（初始全部赋值为 $1$ ，再后面我们用 $f l a g$ 进行代替），如果 $flag_i$ （ $2\le i\le n$ ， $i$ 初始值为 $2$ ）为 true，而由于 $i$ 的倍数肯定包含质因数 $i$ ，所以就要依次将下标为 $i$ 的倍数的位置的值都改成 false，最后将 $i$ 的值加上 $1$ 。通过进行如上操作后， $f l a g$ 数组中值为 true 的位置的下标即为质数。具体的代码如下：

for(int i=2;i<=n;++i) if(flag[i]) for(int j=i;j<=n;j+=i) flag[j]=false;

那么，如何进行改进呢？其实，我们可以不把下标为 $i$ 的倍数的位置的值改成 false，而是改成 $i$ ，而 $i$ 也就是它们当前的最大质因数，如果后面 $i$ 加了若干个 $1$ 之后还是它们之中任意个的质因数，则会更改其最大质因数为现在的 $i$ 。需要注意的一点是，由于埃氏筛的筛法变了，它的判断条件也将改变，并且由于 $f l a g$ 所存储的类型改变成了 int 类型，所以也要将 $f l a g$ 改成 int 类型。

code

#include<iostream>
using namespace std;
int n,b,Max[1000005]/*存储最大质因数*/,ans;
int main() {cin>>n>>b;Max[1]=1;for(int i=2;i<=n;++i) if(!Max[i]) for(int j=i;j<=n;j+=i) Max[j]=i;//找到最大质因数for(int i=1;i<=n;++i) if(Max[i]<=b) ++ans;//判断是否满足要求cout<<ans;return 0;
}