http://projecteuler.net/problem=23

2つの過剰数の和で表せない整数の総和を求めよ。ただし28123より大きい整数についてそのような整数は存在しないことが保証されている。

Rubyで適当に書いたらかなり時間がかかったので最適化。最後の二重ループとfactorでmapを使っているところに高速化の余地あり。

{{{#!highlight c++
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
using namespace std;

#define LIMIT 28123

bool isPrime[LIMIT+1];
vector<int> primes;
vector<int> abundants;

void factor(int n, map<int, int>& fs) {
    for (int i = 0; primes[i] * primes[i] <= n; i++) {
        while (n % primes[i] == 0) {
            n /= primes[i];
            fs[primes[i]]++;
        }
    }
    if (n != 1) fs[n]++;
}

int power(int x, int n) { // x ^ n
    int p = 1;
    for (int i = 0; i < n; i++) {
        p *= x;
    }
    return p;
}

int divisorSum(int n) {
    int sum = 1;
    map<int, int> fs;
    factor(n, fs);
    for (map<int, int>::iterator it = fs.begin(); it != fs.end(); it++) {
        // 約数の和: p ^ (o + 1) / (p - 1)
        //     ただし p: 素因数, o: 出現数
        sum *= (power(it->first, it->second+1) - 1) / (it->first - 1); 
    }
    return sum - n; // その数自身は除く
}

inline bool isAbundant(int n) {
    return divisorSum(n) > n;
}

void init() {
    memset(isPrime, 1, sizeof(isPrime));
    for (int i = 2; i <= LIMIT; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i + i; j <= LIMIT; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 1; i <= LIMIT; i++) {
        if (isAbundant(i)) {
            abundants.push_back(i);
        }
    }
}

int main() {
    init();
    bool possible[LIMIT+1] = {};
    for (int i = 0; i < abundants.size(); i++) {
        for (int j = i; j < abundants.size(); j++) {
            if (abundants[i] + abundants[j] > LIMIT) break;
            possible[abundants[i]+abundants[j]] = true;
        }
    }
    int sum = 0;
    for (int i = 1; i <= LIMIT; i++) {
        if (!possible[i]) {
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}
}}}