2016-9-18 同学去滴滴面试的一道算法题
题目是这样的，对于一个自然数N，如果N为1或者素数，则和为N；否则N可以被分解为若干自然数之和，求最小的和。
我刚开始想的是回溯法，但是应该是不正确的。。。。总之我没想出来，在网上搜到了一种做法
对于任何大于2的自然数a,b：a + b > a * b。如果N = a * b，则 N > a + b。a和b如果是合数，则可以继续被分解下去。那么求N的最小因数和即求N的素质数和。
贴出一段递归的算法：
public static int minSum(int n) {
if ( n < 3 )
return n;
int sum = 0;
for (int i = 2; i <= n / 2; i++) {
// 如果i是n的一个因数
if ( n % i == 0 ) {
if ( isPrime(i) )
return i + minSum(n / i);
}
}
return n;
}
Written on September 18, 2016