トップページに戻る
次のC++のサンプルへ
前のC++のサンプルへ
Problem23 2つの過剰数の和で書き表せない正の整数の総和
問題
完全数とは, その数の真の約数の和がそれ自身と一致する数のことである.
たとえば, 28の真の約数の和は,1+2+4+7+14=28であるので, 28は完全数である.
真の約数の和がその数よりも少ないものを不足数といい,
真の約数の和がその数よりも大きいものを過剰数と呼ぶ.
12は, 1+2+3+4+6=16となるので, 最小の過剰数である.
よって2つの過剰数の和で書ける最小の数は24である.
数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている.
2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが,
この上限を減らすことが出来ていない.
2つの過剰数の和で書き表せない正の整数の総和を求めよ.
ソース
#include <vector>
#include <algorithm>
void main()
{
std::vector<int> KouhoVect;
puts("28123以下の過剰数を抽出中");
for (int I = 1; I <= 28123; I++) {
int YakusuuSum = 0;
for(int J = 1;J <= I; J++){
if(I%J==0 && I!=J)
YakusuuSum+=J;
}
if (YakusuuSum > I) KouhoVect.push_back(I);
}
bool IsExistArr[28123 + 1] = {false};
const int IsExistArrUB = sizeof(IsExistArr)/sizeof(bool)-1;
for(std::vector<int>::iterator it1 = KouhoVect.begin();it1 != KouhoVect.end();it1++){
printf("%dとの和を検証中\n",*it1);
std::vector<int>::iterator it2 = std::lower_bound(KouhoVect.begin(),KouhoVect.end(),*it1);
for(; it2 != KouhoVect.end();it2++){
if (*it1 + *it2 > IsExistArrUB) break;
IsExistArr[*it1 + *it2] = true;
}
}
int SumVal = 0;
for (int I = 1; I <= IsExistArrUB; I++) {
if (IsExistArr[I] == false) SumVal += I;
}
printf("合計=%d\n",SumVal);
}
実行結果
省略
28110との和を検証中
28112との和を検証中
28116との和を検証中
28120との和を検証中
28122との和を検証中
合計=4179871
解説