/*
完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28であるので, 28は完全数である.
真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.
12は, 1+2+3+4+6=16となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.
2つの過剰数の和で書き表せない正の整数の総和を求めよ.
*/
#include <stdio.h>
#include <stdlib.h>
#define N 28123
//真の約数の和を返す。
int divSum(int num) {
int div, sum = 0;
if( num == 0 ) return 0;
for( div = 1; div < num; div++ ) {
if( num % div == 0 ) sum += div;
}
return sum;
}
//num~1までの和を返す。
//int num1Rep(long long int num) {
//
// if( num <= 1 ) {
// return 1;
// }
// return num + num1Rep(num-1);
//}
int main(void) {
int *num, *abund, *abundSum;
int abundCnt = 0, NabundCnt = 0, abundSC = 0, cnt = 0;
long long int sum = 0;
int i, j;
for( i = 1; i <= N; i++ ) {
sum += i;
}
num = (int *)malloc(sizeof(int) * sum);
if( num == NULL ) {
printf("メモリ確保失敗。\n");
exit(0);
}
for( i = 0; i < N; i++ ) num[i] = i+1;
abund = (int *)malloc(sizeof(int) * N);
if( abund == NULL ) {
printf("メモリ確保失敗。\n");
exit(0);
}
for( i = 0; i < N; i++ ) abund[i] = 0;
//過剰数とそうでない数に分ける。
for( i = 1; i <= N; i++ ) {
if( i < divSum(i) ) {
abund[abundCnt] = i;
abundCnt++;
}
}
//2つの過剰数の和を求めて計算できないようにする。
for( i = 0; i < abundCnt; i++ ) {
for( j = i; j < abundCnt; j++ ) {
num[abund[i]+abund[j]-1] = 0;
cnt++;
}
}
for( i = 0; i < cnt; i++ ) {
sum += num[i];
}
printf("%d\n", sum);
return 0;
}