唯一分解定理

算术基本定理：每个大于1的自然数均可唯一分解为质因数的乘积

唯一分解定理（质因数分解）

唯一分解定理，也称为算术基本定理，是数论中的核心定理之一。它指出：

  • 每个大于1的自然数（合数）都可以唯一分解为质数的乘积
  • 不考虑质因数的排列顺序，这种分解是唯一的

定理的数学表达

n = p1a1 × p2a2 × ... × pkak

其中：

  • p1, p2, ..., pk 是质数（p1 < p2 < ... < pk)
  • a1, a2, ..., ak 是正整数（指数）
  • 这种表示形式称为n的标准分解式
示例：

360 = 23 × 32 × 51

1001 = 7 × 11 × 13

17 = 171 (质数本身)

质因数分解算法

算法步骤

质因数分解的经典算法（试除法）：

  1. 初始化：设 i = 2（最小的质数）
  2. 当 i ≤ √n 时，重复以下步骤：
    • 如果 n 能被 i 整除：
      • 记录 i 为质因数
      • 令 n = n / i
    • 否则，i = i + 1
  3. 如果循环结束后 n > 1，则 n 是最后一个质因数

时间复杂度分析

O(√n) - 最坏情况发生在n为质数时，需要遍历到√n
算法示例：分解360
  1. 360 ÷ 2 = 180 (因数: 2)
  2. 180 ÷ 2 = 90 (因数: 2)
  3. 90 ÷ 2 = 45 (因数: 2)
  4. 45 ÷ 3 = 15 (因数: 3)
  5. 15 ÷ 3 = 5 (因数: 3)
  6. 5 ÷ 5 = 1 (因数: 5)
  7. 最终结果：360 = 23 × 32 × 5

代码实现

下面是使用C++实现的质因数分解核心算法：

质因数分解算法 (C++)
C++
#include <iostream>
#include <vector>
#include <cmath>
#include <utility> // for std::pair

using namespace std;

// 函数：质因数分解
vector<pair<int, int>> primeFactorization(int n) {
    vector<pair<int, int>> factors;
    
    // 处理因数2
    if (n % 2 == 0) {
        int count = 0;
        while (n % 2 == 0) {
            count++;
            n /= 2;
        }
        factors.push_back({2, count});
    }
    
    // 处理奇数因数
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                count++;
                n /= i;
            }
            factors.push_back({i, count});
        }
    }
    
    // 如果n是大于2的质数
    if (n > 2) {
        factors.push_back({n, 1});
    }
    
    return factors;
}

int main() {
    int number;
    cout << "请输入一个正整数: ";
    cin >> number;
    
    if (number <= 1) {
        cout << "请输入大于1的正整数！" << endl;
        return 1;
    }
    
    vector<pair<int, int>> factors = primeFactorization(number);
    
    cout << number << " = ";
    for (size_t i = 0; i < factors.size(); i++) {
        cout << factors[i].first;
        if (factors[i].second > 1) {
            cout << "^" << factors[i].second;
        }
        if (i < factors.size() - 1) {
            cout << " × ";
        }
    }
    cout << endl;
    
    return 0;
}

代码说明

  • 该算法首先处理因数2（最特殊的质数）
  • 然后处理所有奇数因数（从3开始，每次加2）
  • 使用vector存储质因数及其指数
  • 时间复杂度为O(√n)，效率较高
  • 输出格式为标准分解式（如 360 = 2^3 × 3^2 × 5）