找指定范围相亲数对

题目-找相亲数 #

亲和数，又称相亲数、友爱数、友好数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。毕达哥拉斯曾说：“朋友是你灵魂的倩影，要像220与284一样亲密。”人和人之间讲友情，有趣的是，数与数之间也有相类似的关系，数学家把一对存在特殊关系的数称为“亲和数”。常言道，知音难觅，寻找亲和数更使数学家绞尽了脑汁。亲和数是数论王国中的一朵小花，它有漫长的发现历史和美丽动人的传说。参考：百科

一对整数是相亲数是说他们各自的所有有效因子（除了自己以外的因子）之和等于另外一个数。比如(220, 284)就是一对相亲数。

• 220 的所有因子：1+2+4+5+10+11+20+22+44+55+110 = 284
• 284 的所有因子：1+2+4+71+142 = 220

给出整数 k，求 1~k 之间的所有相亲数对。

示例 #

给出 300, 返回 [[220, 284]]

分析 #

因子：能被A整除的整数（除了自身）都是A的因子，所以220的因子：1，2，4，5，10，11，20，22，44，55，110

1. 首先要写个函数来计算因子，简单的方法就是循环一遍，找到所有因子。

2. 算相亲数简单的思路就是挨个计算每个数值的所有因子，然后计算因子的和 ，

3. 最后判断相亲数 在不在给的范围。

两层循环，时间复杂度o（n^2）, 明显不是最好的方法。

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

function sumAllFactors(num){
  let sum = 0
  for(let i=1; i< num; i++){
    if(num%i == 0){
      sum += i
    }
  }
  return sum
}
function algorithm(n){
  let res = {}
  , tmp1 = 0, tmp2 = 0, loveNum = [];
  for(let i=1; i< n; i++){
    if(!res[i]){
      tmp1 = sumAllFactors(i)
      if(tmp1 != i){
        tmp2 = sumAllFactors(tmp1)
        res[tmp1] = tmp2
        if(i == tmp2 ){
          loveNum.push([tmp1, tmp2])
        }
      }
    }
  }
  return loveNum
}
function main(...param) {
  console.show("参数：" + param, "结果：" + JSON.stringify(algorithm(param)))
  testPerformance(algorithm, param)
}
main(3000);

请你自动动手试一下：在线编程环境

公式计算法 #

百科里面给了一个计算公式，没有说明完备性。根据公司计算自然是最简单的了。