# 菜鸟的coding · Day 012
寻找最大质因子
题目
小f来到了智慧之神的国度——须弥。在这里，他遇到了可爱的兰那罗。兰那罗们要举办无忧节，需要获取觉堂之树的果实。觉堂之树的果实需要进入觉堂之树的梦境中，帮助它去除污染才能获得。此时的小f已经进入了觉堂之树的梦境，正在它的核心之中去除污染，但是他却遇到了难题。
觉堂之树的污染是一段区间 [l, r]，每个位置的污染需要对其打击特定次数才能去除，而这个次数恰好是这个位置序号的最大质因子。对于位置 i，小f需要击打 i 的最大质因子次数才能去除 i 位置的污染。小f由于连续的战斗已经筋疲力尽，于是他找到了你，希望你能帮他计算出每个位置的打击次数。
输入：两个数 l, r，代表污染区间。
输出：每个位置的打击次数，用空格隔开。
数据范围：2 ≤ l, r ≤ 2000。
样例：
输入
5 10
输出
5 3 7 2 3 5
思路
从 c=2 开始枚举因子，每次找到能整除 x 的 c，就用 while 把 x 中所有的 c 除干净，记录 c 为当前最大质因子。由于小因子都被除尽，当前能整除 x 的 c 一定是质数，不需要额外判素。循环结束后若 x > 1，则 x 本身是最大质因子（它比所有已除尽的小因子都大）。
#include<bits/stdc++.h>
using namespace std;
int maxPrime(int x){
int max=1;
for(int c=2;c*c<=x;c++){
if(x%c==0){
while(x%c==0){
max=c;
x/=c;
}
}
}
if(x>1) max=x;
return max;
}
int main(){
int l,r;
cin>>l>>r;
for(int c=l;c<=r;c++){
cout<<maxPrime(c)<<" ";
}
return 0;
}复杂度分析
- 时间复杂度：O((r−l+1) · √r)，每个数枚举因子到 √x。
- 空间复杂度：O(1)。
今日感受
第一版用 if 除了一次就继续，导致重复因子没除干净，结果错了。改成 while 把同一个因子除到底，才能保证后续遇到的因子一定是质数。还有一个关键：循环结束后如果 x > 1，这个剩余的 x 本身就是最大质因子——因为所有更小的质因子都已经被除掉了。