核心思路:将 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; } }