import java.util.*; class Main{ public static void main(String[] args){ Scanner sc= new Scanner(System.in); int n = sc.nextInt(); int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; for(int i = 2;i<n+1;++i){ dp[i] = i; } for(int i = 2;i<dp.length;++i){ for(int j = i/2;j>=1;--j){ if(i%j==0){ dp[i] = Math.min(dp[i],j+dp[i/j]); } } } System.out.println(dp[dp.length-1]); } } 简单dp