Project Euler 21
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未満の友愛数の合計を求めよ。
Mathematica
tmps = 0; tmp1 = 0; TotalOfDivisors[n_] := Total[Most[Divisors[n]]]; For[i = 2, i < 10000, i++, tmp1 = TotalOfDivisors[i]; If[ i < tmp1 && i == TotalOfDivisors[tmp1], tmps += i + tmp1, {} ] ] tmps
TotalOfDivisors[a] が、問題文の d(a)にあたります。
Most というよくわからない関数が使われていますが、
例えば220を Divisors 関数に渡した場合、 {1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220} が返ってきます。
220自身がいらないので、 『リストの最後の要素を除いたものを返す』Most 関数を使い、Totalで全部足しています。
C/C++
#include <iostream> using namespace std; // nの約数の和を返す。 int divisor_total(int n){ int sum = 1; for(int i=2 ; i<=n/2 ; i++){ if(n%i==0) sum+=i; } return sum; } int main(){ int tmp, sum=0; for(int i=0 ; i<10000 ; i++){ tmp = divisor_total(i); if( i!=tmp && i == divisor_total(tmp)){ sum += i; } } cout << sum << endl; int end; cin >> end; return 0; }
結構楽だった。約数の和を返す関数がもうちょっとどうにかならないものかと思ったけど、10000程度だったら特に支障がないようなので、妥協。