B2138 最大质因子序列 题解

· · 题解

提供一种类似搜索（其实是分解）的思路。

题意

给定 m 和 n，求 n 到 m 区间每个数的最大质因子并输出，用逗号隔开。

思路

我们可以考虑因数分解，把一个整数分解成质数相乘的形式，从最小的质数 2 分解，该质数能整除这个整数就整除它。如果整除它之后就变成 1，就说明是最大的质因子。

至于如果某个数本身是质数，则输出这个数自身的要求，也不用考虑特判，因为除到能被整除时也是输出这个质数。

完整代码

#include<cstdio>
int ans;
void f(int a,int k){
    //a表示当前这个数，k表示除数 
    if(a%k==0){//能被整除 
        if(a/k==1) {
            //如果整除后得1，则记录答案，不用继续分解 
            ans=k;
            return;
        }
        f(a/k,k);//整除 
    }else{
        f(a,k+1);//尝试下一个数 
    } 
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);//输入 
    while(n<=m){
        f(n,2);//调用函数 
        printf("%d",ans);//输出答案 
        if(n!=m) printf(",");//特判是否需要逗号 
        n++;
    }
    return 0;
}

QWQ 谢谢阅读