Project Euler 23
完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28であるので, 28は完全数である. 真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ. 12は, 1+2+3+4+6=16となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない. 2つの過剰数の和で書き表せない正の整数の総和を求めよ.
TotalOfDivisors[n_] := Total[Most[Divisors[n]]]; A = {}; For[i = 1, i < 28123, i++, If[i < TotalOfDivisors[i], A = Append[A, i], {} ] ] A2 = Union[Flatten[ Table[ A + A[[i]], {i, Length[A]} ] ]]; A3 = Select[A2, #<28123 &]; 28122×28123/2 - Total[A3]
力技で何の工夫もないコードになってしまいました。
まず A に 28123 までの過剰数のリストを作り、
A2 で、Aの任意の2数の和のリストを作り、
A3 で、A2の中で 28123以下のものを選びリストにします。
Mathematica
#include <iostream> #include <deque> #include <set> 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; } // nが完全数 -> 0 // nが過剰数 -> 1 // nが不足数 -> -1 int perfectNum(int n){ if(n==divisor_total(n)) return 0; else if(n < divisor_total(n)) return 1; else return -1; } int main(){ deque<int> abundants; set<int> abdsum; for(int i=2 ; i<=28123 ; i++){ if(perfectNum(i)==1){ abundants.push_back(i); } } for(int i=0 ; i<abundants.size() ; i++){ for(int j=i; j<abundants.size() ; j++){ if(abundants[i]+abundants[j] <= 28123) abdsum.insert(abundants[i]+abundants[j]); } } int sum; sum = 28123*28124/2; set<int>::iterator it = abdsum.begin(); while( it!= abdsum.end() ){ sum -= *it; it++; } cout << sum << endl; int end; cin >> end; return 0; }
setを使うと、値を出すのにiteratorを使う必要があるんですね。
計算時間がかなりかかってしまうのがなぁ。これももっと速くしたい。