find all amicable numbers.

1. find all amicable numbers. more info on 1point3acres.com
输入一个正整数，找出所有小于这个数的amicable pairs。讨论了一下时间空间复杂度以及如何tradeoff，最后写了时间复杂度O(n^1.5)，空间复杂度O(n)的算法。

import java.util.ArrayList;

import java.util.List;

public class Solution {

public List<int[]> findAmicable(int num) {

List<int[]> res = new ArrayList<>();

for (int i = 1; i <= num; i++) {

int factorSum = getFactorSum(i);

if (i < factorSum && factorSum <= num) {

int factorSum2 = getFactorSum(factorSum);

if (i == factorSum2) {

res.add(new int[] { i, factorSum });

}

}

}

return res;

}

private int getFactorSum(int num) {

int res = 1;

for (int i = 2; i <= Math.sqrt(num); i++) {

if (num % i == 0) {

res += i;

res += num / i;

}

}

return res;

}

public static void main(String args[]) {

Solution s = new Solution();

List<int[]> res = s.findAmicable(3000);

for (int[] arr : res) {

System.out.println(arr[0] + " " + arr[1]);

}

}

}