题意:
求出所给数字的最大的质因数
考察知识点:
枚举,数学
时间复杂度 :O(根号n)
思路分析:
1)求质因数,对于数n,若其中一个质因子为d,则另一个为n/d,它们是成对出现的;
2)有1)可得我们可以求出较小的质因子,即可得到与其成对的较大的质因子
3)d<=n/d 推出 d<=根号n
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int main(){
scanf("%d",&n);
for(int i = 2;i;i++){
if(n%i==0){
cout << n/i;
break;
}
}
return 0;
}