自动搬运

查看原文

来自洛谷，原作者为

	Kingna We live and die in the shadows for those we hold close and for those we never meet.

搬运于2025-08-24 21:07:38，当前版本为作者最后更新于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;//最后是不输出空格的 
	}
}