一、唯一分解定理基础

任意大于1的正整数均可唯一表示为若干不同质数幂的乘积：

其中 p₁, p₂, ..., pₘ 为互异质数，k₁, k₂, ..., kₘ 为其对应指数。该定理为整数结构分析提供了理论基础。

1.1 质因数分解实现

分解步骤：

1. 从最小质数2开始试除目标数 n
2. 若可整除则持续除尽并记录指数
3. 递增试除因子直至 i ≤ √n
4. 若最终 n > 1 则其本身为质因子

import java.util.*;

public class PrimeFactorization {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        List<int[]> factors = new ArrayList<>();
        
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                int exp = 0;
                while (num % i == 0) {
                    exp++;
                    num /= i;
                }
                factors.add(new int[]{i, exp});
            }
        }
        if (num > 1) factors.add(new int[]{num, 1});
        
        factors.forEach(f -> System.out.println(f[0] + " " + f[1]));
    }
}

二、约数个数计算

2.1 公式原理

若 n = p₁ᵏ¹ × p₂ᵏ² × ... × pₘᵏᵐ，则约数个数为：

2.2 阶乘约数个数计算

public class FactorialDivisors {
    public static void main(String[] args) {
        int n = 100;
        int[] primeExponents = new int[n + 1];
        
        // 统计每个质因子在n!中的总指数
        for (int i = 2; i <= n; i++) {
            int temp = i;
            for (int j = 2; j * j <= temp; j++) {
                while (temp % j == 0) {
                    primeExponents[j]++;
                    temp /= j;
                }
            }
            if (temp > 1) primeExponents[temp]++;
        }
        
        long divisorCount = 1;
        for (int exp : primeExponents) {
            if (exp > 0) divisorCount *= (exp + 1);
        }
        System.out.println(divisorCount);
    }
}

三、约数和计算

3.1 公式原理

约数和公式为各质因子等比数列和的乘积：

3.2 单数约数和计算

import java.util.Scanner;

public class SingleNumberDivisorSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int original = n;
        int[] exponents = new int[n + 1];
        
        // 质因数分解
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                exponents[i]++;
                n /= i;
            }
        }
        if (n > 1) exponents[n] = 1;
        
        // 计算约数个数
        long count = 1;
        for (int exp : exponents) {
            if (exp > 0) count *= (exp + 1);
        }
        
        // 计算约数和
        long sum = 1;
        for (int p = 2; p <= original; p++) {
            if (exponents[p] == 0) continue;
            long geometricSum = 0;
            long power = 1;
            for (int j = 0; j <= exponents[p]; j++) {
                geometricSum += power;
                power *= p;
            }
            sum *= geometricSum;
        }
        
        System.out.println(original + " 的约数个数：" + count);
        System.out.println(original + " 的约数和：" + sum);
    }
}

3.3 阶乘约数和计算

import java.math.BigInteger;

public class FactorialDivisorSum {
    public static void main(String[] args) {
        int n = 100;
        int[] exponents = new int[n + 1];
        
        // 统计质因子指数（同约数个数逻辑）
        for (int i = 2; i <= n; i++) {
            int temp = i;
            for (int j = 2; j * j <= temp; j++) {
                while (temp % j == 0) {
                    exponents[j]++;
                    temp /= j;
                }
            }
            if (temp > 1) exponents[temp]++;
        }
        
        // 约数个数计算
        long count = 1;
        for (int exp : exponents) {
            if (exp > 0) count *= (exp + 1);
        }
        
        // 约数和计算（使用BigInteger防溢出）
        BigInteger sum = BigInteger.ONE;
        for (int p = 2; p <= n; p++) {
            if (exponents[p] == 0) continue;
            
            BigInteger base = BigInteger.valueOf(p);
            BigInteger geoSum = BigInteger.ZERO;
            BigInteger current = BigInteger.ONE;
            for (int j = 0; j <= exponents[p]; j++) {
                geoSum = geoSum.add(current);
                current = current.multiply(base);
            }
            sum = sum.multiply(geoSum);
        }
        
        System.out.println("100! 的约数个数：" + count);
        System.out.println("100! 的约数和：" + sum);
    }
}