题解 | 矩形游戏-Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        System.out.println(maxScore(n));
        scanner.close();
    }
    
    private static long maxScore(long n) {
        long score = 0;
        
        // 贪心策略：每次选择当前数的最大真因子作为下一个数
        while (n > 1) {
            score += n;
            // 找到n的最小质因子
            long smallestPrime = smallestPrimeFactor(n);
            // 最大真因子 = n / 最小质因子
            n = n / smallestPrime;
        }
        
        // 最后加上1（游戏结束时的石子数）
        score += 1;
        return score;
    }
    
    // 寻找n的最小质因子
    private static long smallestPrimeFactor(long n) {
        // 偶数的最小质因子是2
        if (n % 2 == 0) {
            return 2;
        }
        
        // 检查奇数因子，从3开始，步长为2
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return i;
            }
        }
        
        // 如果没有找到因子，说明n是质数，其最小质因子是自身
        return n;
    }
}