プロジェクトオイラー問23

Problem 23 「非過剰数和」 †

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28 であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.

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

解法
メモ化計算するだけ
C++

#include<stdio.h>
#include<vector>
#include<string.h>
const int LIMIT=28124;

int main(){
       int yakusu_sum[LIMIT]={0};
       for(int i=1;i<LIMIT;i++){
              for(int j=i*i;j<LIMIT;j+=i){
                     yakusu_sum[j]+=i+(j/i)*(i>1&&i*i!=j);
              }
       }
       std::vector<int> kazyo;
       for(int i=12;i<LIMIT;i++){
              if(yakusu_sum[i]>i)kazyo.push_back(i);
       }
       bool addOK[LIMIT];
       memset(addOK,true,sizeof(addOK));
       for(int i=0;i<kazyo.size();i++){
              for(int j=i;j<kazyo.size();j++){
                     if(kazyo[i]+kazyo[j]>=LIMIT)break;
                     addOK[kazyo[i]+kazyo[j]]=false;
              }
       }
       int ans=0;
       for(int i=1;i<LIMIT;i++){
              ans+=addOK[i]*i;
       }
       printf("%d\n",ans);
}