B2138 最大质因子序列

Kingna · 2021-07-15 19:34:40 · 题解

大家好，又跟大家见面了！

题意

给定一个区间 [m,n] 求区间内所有整数的最大质因子并依次输出

思路

大约 csp-pg 第一题的难度。

首先，这道题说了求最大质因子，那么想都不用想，先把判断质数的函数打出来。

int w(int i){//判断i是否为质数 
    if(i==2){
        return 1;//特判 
    }
    for(int j=2;j<=sqrt(i);j++){//这里是枚举到 sqrt(j) 的，因为一个数的因数最大是 sqrt(j)  
        if(i%j==0){
            return 0;//就不是质数了 
        }
    } 
    return 1;//否则为质数 
}

然后题目中说了是求最大的，所以倒着枚举（当然你正着也没什么，只是耗时太大，也不好想）。

下面是求最大质数的函数

void zhi(int i){//因为我们是在函数中直接输出的，所以是void 类型
    for(int j=i;j>=2;j--){//说了的是倒着枚举！这个时候必须从i往下走，因为万一i是质数呢？
        if(i%j==0&&w(j)==1){//找到了因子，并且这个因子是质数就输出
            cout<<j;
            break;
        }
    }
}

再加上那个很短的主函数

int main(){
    cin>>n>>m;//n,m含义看题 
    for(int i=n;i<=m;i++){
        zhi(i);//执行函数，求i的最大质因子
        if(i!=m){ //如果你没明白为什么这样做，那么请把这个if删去，也把cout<<endl删去，看看会发生什么 
            cout<<",";
        }
        else cout<<endl;//最后是不输出空格的 
    }
}