# 相亲数
# 难度：简单
# 描述：
一对整数是相亲数是说他们各自的所有有效因子（除了自己以外的因子）之和等于另外一个数。比如(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~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
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
- 在求因素和的时候，直接判断是否有对应的相亲数
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
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