分解质因数

思路

经典的质因数分解问题。给一个正整数 n，把它拆成若干个质因数的乘积，从小到大输出。

核心思路非常简单：从最小的质数 2 开始，能整除就一直除，除完了再试下一个数。为什么不需要专门判断 i 是不是质数？因为当我们试到 i 的时候，所有小于 i 的因子已经被除干净了，所以如果 n 能被 i 整除，i 必然是质数。

一个关键优化：只需要枚举到 。如果循环结束后 n 还大于 1，说明剩下的 n 本身就是一个质因数（最大的那个）。

举个例子：n = 60

  • i = 2: 60 / 2 = 30, 30 / 2 = 15，输出两个 2
  • i = 3: 15 / 3 = 5，输出一个 3
  • i = 4: 5 % 4 != 0，跳过
  • 此时 i*i = 25 > 5，循环结束，n = 5 > 1，输出 5
  • 结果：2 2 3 5

代码

#include <cstdio>
using namespace std;
int main(){
    long long n;
    scanf("%lld",&n);
    bool first=true;
    for(long long i=2;i*i<=n;i++){
        while(n%i==0){
            if(!first) printf(" ");
            printf("%lld",i);
            first=false;
            n/=i;
        }
    }
    if(n>1){
        if(!first) printf(" ");
        printf("%lld",n);
    }
    printf("\n");
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        StringBuilder sb = new StringBuilder();
        for (long i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                if (sb.length() > 0) sb.append(' ');
                sb.append(i);
                n /= i;
            }
        }
        if (n > 1) {
            if (sb.length() > 0) sb.append(' ');
            sb.append(n);
        }
        System.out.println(sb.toString());
    }
}

import math

n = int(input())
factors = []
i = 2
while i * i <= n:
    while n % i == 0:
        factors.append(str(i))
        n //= i
    i += 1
if n > 1:
    factors.append(str(n))
print(' '.join(factors))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let n = BigInt(lines[0].trim());
    const factors = [];
    for (let i = 2n; i * i <= n; i++) {
        while (n % i === 0n) {
            factors.push(i.toString());
            n /= i;
        }
    }
    if (n > 1n) {
        factors.push(n.toString());
    }
    console.log(factors.join(' '));
});

复杂度分析

  • 时间复杂度: ，最坏情况下枚举到 。
  • 空间复杂度: ，只用了常数个变量。

小结

质因数分解是数论的基础操作，思路很直接：从小到大试除，能除就除到底。核心技巧是只枚举到 ，因为一个合数最多只有一个大于 的质因子，循环结束后如果 n > 1 就把它补上。这个模板在很多数论题里都会用到，值得记住。