※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「プロジェクトオイラー問い21~30」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問い21~30 - (2012/12/14 (金) 19:17:37) の編集履歴(バックアップ)


問い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未満の友愛数の和を求めよ.

解法
コードの中では1~nまでの約数を求める計算はsetYakusuu関数で簡単に方がついてます。
後は条件を満たすかどうかmain関数のなかで調べるだけです。


#include<stdio.h>
const int up=10000;
int memo[up+1]={0};
void setYakusuu(){
for(int i=1;i<=up;i++){
	for(int j=2*i;j<=up;j+=i){
		memo[j]+=i;
	}
}
}


int main(){
setYakusuu();
int d,ans=0;
for(int i=2;i<up;i++){
	d=memo[i];
	if(d<up&&memo[d]==i&&d!=i){
		printf("%d %d\n",d,i);
		ans+=i;
	}
}
printf("%d",ans);
}