【题目描述】
求一个合数的最大质因子。

【算法分析】
○ 一个合数 n 的非本身的最大因子为 n/2。
○ 判断素数的代码：https://blog.csdn.net/hnjzsyjyj/article/details/119729401

#include <bits/stdc++.h>
using namespace std;bool isPrime(int n) {if(n<2) return false;for(int i=2; i<=sqrt(n); i++) {if(n%i==0) return false;}return true;
}int main() { //Find the primes between 2 and nint n;cin>>n;for(int i=2; i<=n; i++) {if(isPrime(i)) cout<<i<<" ";}
}/*
in:
100
out:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
*/

○ 若 n 是合数，则在 1~sqrt(n) 范围内进行因子判别。简证如下：
给定一个数字 n，朴素的求其因子的方法为枚举 [1,n] 的所有数进行余数为 0 判定，算法时间复杂度为 O(n)。此处加入一个小优化，即若 m 为 n 的因子，那么 n/m 必然也为 n 的因子，不妨设 m≤n/m，则有 m≤sqrt(n)，所以只需在 [1,sqrt(n)] 内枚举所有数进行余数为 0 判定即可，算法时间复杂度优化为 O(sqrt(n))。

【算法代码】

#include <bits/stdc++.h>
using namespace std;void maxPrimeFactor(int n) {int ans=0;for(int i=n/2; i>1; i--) {if(n%i==0) {bool flag=true;for(int j=2; j*j<=i; j++) {if(i%j==0) {flag=false;break;}}if(flag && i>ans) ans=i;}}cout<<ans<<endl;
}int main() {int n;cin>>n;maxPrimeFactor(n);return 0;
}/*
in:180
out:5
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/119729401
https://blog.csdn.net/hnjzsyjyj/article/details/138047200
https://blog.csdn.net/hnjzsyjyj/article/details/138084023
https://blog.csdn.net/joe_g12345/article/details/135307949
https://blog.csdn.net/hnjzsyjyj/article/details/138091319