「プロジェクトオイラー問２１」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問２１ - (2014/02/14 (金) 13:06:06) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2021


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


解法
原理主義的に約数の集合を得てそれを集計するという手法で解いてみました。
約数の和を述語で計算して、それが10000以下でもう一度約数の和を求める述語に通してもとに戻ればそれは友愛数。
配列が使える言語ならもう少し賢い方法があります。



 yakusu(_,1,1):-!.
 yakusu(N,P,P):-N mod P=:=0.
 yakusu(N,P,N1):-N>P*P,N mod P=:=0,!,N1 is N // P.
 
 sum([],0):-!.
 sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X.
 
 yakusu_list(N,Y1):-
 	between(1,N,Y),
 	Y2 is Y*Y,
 	(Y2>N->!,fail;true),
 	yakusu(N,Y,Y1).
 yakusu_sum(N,Sum):-
  	findall(Y,yakusu_list(N,Y),Ys),
 	sum(Ys,Sum).
 
 fSearch(N):-
  	between(1,9999,N),
	yakusu_sum(N,N1),
          N1=<9999,
 	N1=\=N,
 	yakusu_sum(N1,N).
 
 main21:-
 	findall(N,fSearch(N),AnsList),
 	sum(AnsList,Ans),
 	write(Ans).





同じ問題をC++で解いたもの。
ある数の約数を求めるのではなく、約数の定数倍に約数を積みたてていくと考える。
計算量61622回、そんなに大差はないけれど少しだけ早いかな。


 #include<stdio.h>
 #include<math.h>
 
 const int MAX=10000;
 int memo[MAX]={0};
 int main(){ 
 	int count=0;
 	int Down=sqrt(MAX);
 	for(int i=1;i*i<MAX;i++){
  		for(int k=2;k*i<MAX;k++){
			int p=k*i;
 			memo[p]+=i;
 			count++;
 			if(Down<=k&&i>1)memo[p]+=k;
  		}
	}
 	int ans=0;
 	for(int i=1;i<MAX;i++){
 		int t=memo[i];
  		if(t!=i&&t<MAX&&i==memo[t]){
 			ans+=i;
 		}
		count++;
 	}
 	printf("ans=%d 計算量=%d\n",ans,count);
 }