如何高效寻找合数的最大质因数

1. 题目解析与解题思路

这道题目要求我们找到一个合数n的最大质因数。题目描述虽然简单，但有几个关键点需要注意：

1. 输入范围：n ≤ 2×10^9
2. 输出要求：n的最大质因数
3. 题目保证n是两个不同质数的乘积

1.1 题目核心理解

题目给出的关键信息是"n是两个不同质数的乘积"，这意味着：

• n本身是一个合数（非质数）
• n只有两个质因数（因为质数乘以质数）
• 这两个质因数不相同

因此，我们实际上只需要找到n的两个因数中较大的那个质数即可。

1.2 解题思路分析

基于题目特性，我们可以采用以下方法：

1. 从2开始遍历到√n，寻找n的因数
2. 找到的第一个能整除n的数i，必然是较小的那个质因数
3. 另一个因数就是n/i，也就是较大的质因数
4. 直接返回n/i即可

这种方法的正确性基于以下数学原理：

• 任何合数n的最小质因数都不会超过√n
• 题目保证n只有两个质因数，所以第一个找到的因数就是较小的那个

2. 代码实现与优化

2.1 原始代码分析

原始代码的思路是：

1. 遍历1到√n的所有整数i
2. 如果i是n的因数，检查n/i是否是质数
3. 记录最大的满足条件的质因数

cpp复制#include<iostream>
#include<vector>
using namespace std;

bool sushu(long long m) {
    if (m <= 1) return false;
    if (m == 2) return true;
    if (m % 2 == 0) return false;
    for (long long i = 3; i * i <= m; i += 2) {
        if (m % i == 0) return false;
    }
    return true;
}

int main() {
    long long m;
    cin >> m;
    long long max = 0;
    for (long long i = 1; i * i <= m; i++) {
        if (m % i == 0) {
            long long othe