首页 > 代码库 > Snapchat - Amicable Pair

Snapchat - Amicable Pair

2024-08-16 01:32:09   238人阅读

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

1         for(int i = 2; i <= n / 2; i++) {2             for(int j = i * 2; j <= n; j += i) {3                 factorSum[j] += i;4             }5         }

道理是，比如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

然后统计

 

代码：

 1 public class AmicableNumber { 2     public List<List<Integer>> findAmicablePair(int n) { 3         List<List<Integer>> res = new ArrayList<>(); 4         if(n <= 2) { 5             return res; 6         } 7         int[] factorSum = new int[n + 1]; 8         for(int i = 0; i <= n; i++) { 9             factorSum[i] = 1;10         }11         for(int i = 2; i <= n / 2; i++) {12             for(int j = i * 2; j <= n; j += i) {13                 factorSum[j] += i;14             }15         }16         //System.out.println(factorSum[10000] + " " + factorSum[23000] );17         Map<Integer, Integer> map = new HashMap<>();18         for(int i = 2; i <= n; i++) {19             if(map.containsKey(i) && factorSum[i] == map.get(i)) {20                 ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(factorSum[i], i));21                 res.add(list);22             } else {23                 map.put(factorSum[i], i);24             }25         }26         return res;27     }28     29     public static void main(String[] args) {30         //[[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368], 31         //[10744, 10856], [12285, 14595], [17296, 18416], [66928, 66992]]32         AmicableNumber sample = new AmicableNumber();33         System.out.println(sample.findAmicablePair(66992));34     }35 }

 

Snapchat - Amicable Pair


联系
我们