https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_amicable_pair.html
输入一个正整数，找出所有小于这个数的amicable pairs。讨论了一下时间空间复杂度以及如何tradeoff，最后写了时间复杂度O(n^1.5)，空间复杂度O(n)的算法。
Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number.
Amicable number（相亲数）定义：
相亲数（Amicable Pair），又称亲和数、友爱数、友好数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。
例如220与284：
220的全部约数（除掉本身）相加是：1+2+4+5+10+11+20+22+44+55+110=284 284的全部约数（除掉本身）相加的和是：1+2+4+71+142=220
相关题目1：给定整数n，找到小于n的所有amicable number的和
相关知识：
1、比如36 = 2^2 + 3 ^2。那么它有两个2和三个3是它的质因数，它有（2+1）*（2+1）= 9个约数，因为可以选0个2，1个2或者3个2，对于3同理。
2. 还有一点：如果factorSum表示这个数所有约数的和，那么 b = factorSum(a), c = factorSum(b), 如果c == a 并且 a != b，那么a和b就是相亲对
所以这题的算法是，找到所有小于根号n的prime number。
对于所有小于n的整数：
res = 0;
sum = factorSum(i);
if(factorSum(sum) == i && i != sum) {
res += sum;
}
本道题目：给定整数n，求出所有小于n的相亲数
思路：
求出从1-n所有数的factorSum
for(int i = 2; i <= n / 2; i++) {
for(int j = i * 2; j <= n; j += i) {
factorSum[j] += i;
}
}
道理是，比如n = 20 i = 2，那么4，6，8，10，...，20位置上的sum都+2
i = 3，那么6,9,12,15,18位置上的都+3
时间复杂度O(nlogn). 外层是O(n)内层是1/2+1/3+...+1/n ~ logn
然后统计
public class AmicableNumber {
public List<List<Integer>> findAmicablePair(int n) {
List<List<Integer>> res = new ArrayList<>();
if(n <= 2) {
return res;
}
int[] factorSum = new int[n + 1];
for(int i = 0; i <= n; i++) {
factorSum[i] = 1;
}
for(int i = 2; i <= n / 2; i++) {
for(int j = i * 2; j <= n; j += i) {
factorSum[j] += i;
}
}
//System.out.println(factorSum[10000] + " " + factorSum[23000] );
Map<Integer, Integer> map = new HashMap<>();
for(int i = 2; i <= n; i++) {
if(map.containsKey(i) && factorSum[i] == map.get(i)) {
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(factorSum[i], i));
res.add(list);
} else {
map.put(factorSum[i], i);
}
}
return res;
}
public static void main(String[] args) {
//[[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368],
//[10744, 10856], [12285, 14595], [17296, 18416], [66928, 66992]]
AmicableNumber sample = new AmicableNumber();
System.out.println(sample.findAmicablePair(66992));
}
}输入一个正整数，找出所有小于这个数的amicable pairs。讨论了一下时间空间复杂度以及如何tradeoff，最后写了时间复杂度O(n^1.5)，空间复杂度O(n)的算法。
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]);
}
}
https://en.wikipedia.org/wiki/Amicable_numbersAmicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number.
The smallest pair of amicable numbers is (220, 284). They are amicable because the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71 and 142, of which the sum is 220.
