相亲数

难度:简单

描述:

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

思路分析:

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

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

代码模板:

const amicablePair = k => {};
1

想一想再看答案

想一想再看答案

想一想再看答案

代码:

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

  1. 遍历 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));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 在求因素和的时候,直接判断是否有对应的相亲数
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; // 结果
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

鼓励我一下:

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

Last Updated: 11/4/2018, 3:47:41 PM