Project Euler: Problem23

現在は工場実習中で毎日肉体労働をしてるので、休日くらいはプログラムを書きたくなります。というわけで超久しぶりに Project Euler をやってみたよ。

問題23。正の整数 n の約数の和が n をより大きいとき、 n を過剰数(abundant number)という。2つの過剰数の和で表すことができない正の整数の和を求めよ。ただし28123より大きい整数は2つの過剰数の和で表せることがわかっている。

Haskell で適当に書いたら止まらなかったので C で書き直した。

#include <stdio.h>
#define MAX 28123

int sumOfFactors(int n){
  int x,r;
  for (x=1,r=0;x<n;x++)
    if (n%x==0)
      r += x;
  return r;
}

int main(){
  char abundands[MAX];
  char result[MAX];
  unsigned int sum = 0;
  int i,j;

  for (i=0;i<MAX;i++)
    result[i] = 0;

  for (i=0;i<MAX;i++)
    abundands[i] = sumOfFactors(i) > i;

  for (i=0;i<MAX/2;i++)
    if (abundands[i])
      for (j=i;j+i<MAX;j++)
        if (abundands[j])
          result[i+j] = 1;

  for (i=0;i<MAX;i++)
    if (!result[i])
      sum += i;

  printf("%u\n", sum);
  return 0;
}