算法-相亲数

相亲数

难度：简单

描述：

一对整数是相亲数是说他们各自的所有有效因子（除了自己以外的因子）之和等于另外一个数。比如(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]]

思路分析：

因素：给出一个数，能整除该数的的除数都是这个数的因素。

计算出每个数的因素和，将其存起来，然后再去判断是否为相亲数

代码模板：

1	const amicablePair = k => {};

想一想再看答案

代码：

事实上我们要做的只有两步：

遍历 1~k 求出每个数的因素和，并用对象存储起来,遍历对象，判断相亲数

const amicablePair = k => {
  let obj = {};
  // 遍历整个范围，包括k
  for (let i = 1; i <= k; i++) {
    let arr = [];
    // 求每个数的因数
    for (let j = 1; j < i; j++) {
      // 能整除 没有余数的 除数都是因数
      if (i % j === 0) {
        arr.push(j);
      }
    }
    // 计算因数和
    let total = arr.reduce((a, b) => {
      return a + b;
    }, 0);
    obj[i] = total; // 储存每个数的相亲数
  }
  let res = []; // 结果
  for (let key in obj) {
    // 顺序 当属性的值比属性大时才进入 此处也可防止重复添加
    if (obj[key] > key) {
      // 判断相亲数
      if (key === `${obj[obj[key]]}`) {
        res.push([key, obj[key]]); // 按顺序添加
      }
    }
  }
  return res;
};
console.log('输出', amicablePair(300));

在求因素和的时候，直接判断是否有对应的相亲数

const amicablePair = k => {
  let res = [];
  // 遍历整个范围，包括k
  for (let i = 1; i <= k; i++) {
    let total = totalFn(i);
    // i的因素和需要比i小 才能push 防止重复添加
    if (total > i) {
      let total2 = totalFn(total); // 求 i的因素和 的因素和
      // 判断相亲数：i是否与i的因素和的因素和相等
      if (i === total2) {
        res.push(i, total);
      }
    }
  }
  // 计算一个数的因素和
  function totalFn(num) {
    let arr = [];
    // 求每个数的因数
    for (let j = 1; j < num; j++) {
      // 能整除 没有余数的 除数都是因数
      if (num % j === 0) {
        arr.push(j);
      }
    }
    // 计算因数和
    let total = arr.reduce((a, b) => {
      return a + b;
    }, 0);
    return total;
  }
  return res; // 结果
};

鼓励我一下：

觉得还不错的话，给我的项目点个star吧