找指定范围相亲数对

题目-找相亲数

亲和数,又称相亲数友爱数友好数,指两个正整数中,彼此的全部约数之和(本身除外)与另一方相等。毕达哥拉斯曾说:“朋友是你灵魂的倩影,要像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);

 

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

公式计算法

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

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 找指定范围相亲数对

赞 (3) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏