Project Euler 問題23（過剰数の和でない数）を解いてみる

#include <stdio.h>

#define LIMIT 28123

int abundant[LIMIT + 1];
int is_sum_of_abundant[LIMIT + 1];

int calc_sum_of_divisors(int number)
{
	int sum;
	int i;

	sum = 1; /* Add 1 (the first divisor) */
	for (i = 2; i * i <= number; ++i) {
		if ((number % i) == 0) {
			if (i * i != number) {
				sum += i;
				sum += number / i;
			} else {
				sum += i;
			}
		}
	}

	return sum;
}

int main(void)
{
	int i, j;
	int num_of_abundant;
	int sum = 0;

	for (i = 0; i <= LIMIT; ++i) {
		abundant[i] = 0;
		is_sum_of_abundant[i] = 0;
	}

	num_of_abundant = 0;
	for (i = 2; i <= LIMIT; ++i) {
		if (calc_sum_of_divisors(i) > i) {
			abundant[num_of_abundant] = i;
			++num_of_abundant;
		}
	}

	for (i = 0; i < num_of_abundant; ++i) {
		for (j = i; j < num_of_abundant; ++j) {
			if (abundant[i] + abundant[j] <= LIMIT) {
				is_sum_of_abundant[abundant[i] + abundant[j]] = 1;
			}
		}
	}

	for (i = 1; i <= LIMIT; i++) {
		if (is_sum_of_abundant[i] == 0) {
			sum += i;
		}
	}

	printf("Problem023: %d\n", sum);

	return 0;
}