质因数分解算法优化与实现详解

1. 题目背景与需求分析

洛谷P1075是一道经典的质因数分解练习题，题目要求给定一个正整数n（n∈[2,2×10^9]），输出其最大的质因数。这道题看似简单，但考察了以下几个核心知识点：

1. 质数的定义与判断方法
2. 因数分解的基本原理
3. 算法效率优化技巧

在实际解题过程中，我们需要特别注意n的范围可能很大（最大到20亿），因此暴力解法会导致时间复杂度过高，必须采用优化策略。

2. 质因数分解基础原理

2.1 质数与合数

质数是指大于1的自然数，除了1和它本身外没有其他因数。合数则是可以被其他数整除的数。根据算术基本定理，每个大于1的整数都可以唯一表示为质数的乘积。

2.2 因数分解方法

最直观的质因数分解方法是试除法：从最小的质数2开始，依次尝试能否整除目标数n。如果能整除，就将这个质数作为因数，然后对商继续分解，直到商为1为止。

例如分解36：

• 36 ÷ 2 = 18
• 18 ÷ 2 = 9
• 9 ÷ 3 = 3
• 3 ÷ 3 = 1
  所以36 = 2×2×3×3

3. 算法实现与优化

3.1 基础实现思路

最基础的实现代码如下：

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

int main() {
    int n;
    cin >> n;
    
    for(int i=2; i<=n; i++) {
        while(n%i == 0) {
            n /= i;
            if(n == 1) {
                cout << i;
                return 0;
            }
        }
    }
    return 0;
}

这个算法的时间复杂度是O(n)，对于n=2×10^9的情况会非常慢，无法通过时间限制。

3.2 关键优化点

优化主要基于以下数学原理：

1. n的质因数最多只有一个大于√n
2. 如果n是合数，必有一个不大于√n的质因数

因此我们只需要检查2到√n的范围即可：

cpp复制#include <iostream>
#include <cmath>
u