project Euler 021

環境

• javascript

問題

d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.

それでは10000未満の友愛数の和を求めよ.

考え方

1. 1から10000までの数を数え上げる。
2. その数の約数の和を計算する
3. 2.の和からさらに約数の和を計算する
4. 数え上げの数字と3.の約数の和が等しい時、それらの数字を友愛数とし、配列に格納しておく
5. 数え上げが終了した後、配列内の友愛数の和を計算する

コード

let limit = 10000;
let yuaisuList: number[] = [];
for (let a = 2; a < limit; a++) {
  let yakusuAList = [1];
  let yakusuBList = [1];
  for (let i = 2; i < a; i++) {
    if (a % i === 0) {
      yakusuAList.push(i);
    }
  }
  let sumA = yakusuAList.reduce((a, b) => a + b);
  for (let i = 2; i < sumA; i++) {
    if (sumA % i === 0) {
      yakusuBList.push(i);
    }
  }
  let sumB = yakusuBList.reduce((a, b) => a + b);
  if (
    a === sumB &&
    !yuaisuList.find(yuaisu => yuaisu === a) &&
    sumA !== sumB
  ) {
    yuaisuList.push(a);
    yuaisuList.push(sumA);
  }
}
return yuaisuList.reduce((a, b) => a + b);

説明

• 数え上げ数は2から始める。その場合、約数リストには必ず1が格納されている
• まず、数え上げ数の約数を算出し、yakusuAlistに格納する
• yakusuAlistの和を計算し、今度はその和の約数を算出し、yakusuBlistに格納する
• yakusuBlistの和を計算し、友愛数であるかどうかを条件分岐し、友愛数であれば、友愛数リストに格納する
• 数え上げ終了後、友愛数リストの和を計算する