核心思路:将 N 分解为质因数的乘积,最小成本就是所有质因数(包括重复的)之和。

原因:当 a, b>=2 时,a+b<=a*b 恒成立,因此分解为(最小)质因数的成本最低。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.close();

        System.out.println(minCost(N));
    }

    private static int minCost(int n) {
        if (n == 1) return 0;

        int cost = 0;

        // 分解质因数
        for (int i = 2; i * i <= n; i++) {
            // 计算质因数i的指数
            while (n % i == 0) {
                cost += i;  // 累加质因数作为成本
                n /= i;
            }
        }

        // 如果剩余的n是一个质数
        if (n > 1) {
            cost += n;
        }

        return cost;
    }
}