2022年9月1日 哔哩哔哩基础架构第一批编程题：自然数

import java.util.*;
import java.lang.Math;

public class Main {

    public static void main(String[] args){
         Scanner in = new Scanner(System.in);
         int n = in.nextInt();
         int[] dp = new int[n+1];
         for(int i = 2; i <= n; i++){
             if(isPrime(i))  dp[i] = i;
         }
         int sum = 0;
         List<Integer> result = dfs(n, dp);
         for(int i = 0; i < result.size(); i++){
             sum += result.get(i);
         }
        System.out.println(sum);

    }
    public static List<Integer>  dfs(int n, int[] dp ){
        List<Integer> ans = new ArrayList<Integer>();
        if(dp[n] != 0){
            ans.add(dp[n]);
            return ans;
        }
        List<Integer> ansLeft  = new ArrayList<Integer>();
        List<Integer> ansright = new ArrayList<Integer>();

        int left = 0, right = 0;
        int mid = (int)Math.sqrt(n);

        for(int i = mid; i>=2; i--){
            if(n % i != 0){
                continue;
            }else {
                left = i;
                right = n / i;
                ansLeft  = dfs(left,  dp);
                ansright = dfs(right, dp);
                break;
            }
        }
        int sumLeft=0, sumRight = 0;
        for(int i=0;i<ansLeft.size();i++){
            int key = ansLeft.get(i);
            ans.add(key);
            sumLeft += key;
        }
        dp[left] = sumLeft;
        for(int i=0;i < ansright.size();i++){
            int key = ansright.get(i);
            ans.add(key);
            sumRight += key;
        }
        dp[right] = sumRight;
        return  ans;
    }

    public static boolean isPrime(int n){
        int a = (int) Math.sqrt(n);
        for(int i = a;i >= 2; i--){
            if(n % i == 0)  return false;
        }
        return  true;
    }

}