b3969专题

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

思路 我们只要求出每个数的最大质因数,再一个个判断是否满足要求即可。 如何找到每个数的最大质因数呢?其实,我们可以在埃氏筛法的基础上进行改进,从而达到算出最大质因数的目的。 让我们先来了解一下埃氏筛法,知道的人可以跳过。埃氏筛法,首先定义一个 bool 型数组(初始全部赋值为 1 1 1,再后面我们用 f l a g flag flag 进行代替),如果 f l a g i flag_