「プロジェクトオイラー問21」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー問21」(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); }
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); }

表示オプション

横に並べて表示:
変化行の前後のみ表示: