Project Euler의 23번 문제
"2개의 Abundant Number의 합으로 표현할 수 없는 모든 양의 정수의 합을 구하여라"
(단, 28123보다 큰 정수는 모두 2개의 Abundant Number의 합으로 표현할 수 있다)
http://projecteuler.net/index.php?section=problems&id=23

#include <stdio.h>
#define TRUE 1
#define FALSE 0

int isAbundantNumber(int);
int sumOfDivisors(int );

int main(void){
    int  i,j,n,sum;
    int  abun[6965];
        for(i=1;i<28124;i++){
        if(isAbundantNumber(i) == TRUE){
            abun[j]=i;
            j++;
        }
    }
    for(i=1;i<28124;i++){
        if(isRepresentable(i, abun)==TRUE){
            n+=i;
        }
    }
    n = (28123*28124/2)-n;
    printf("The answer is %d\n", n);
    return TRUE;
}

int isAbundantNumber(int  a){
    if(a<sumOfDivisors(a)){
        return TRUE;
    }
    else{
        return FALSE;
    }               
}

int isRepresentable(int a, int *b){
    int i,j,sum;
    for(i=0;i<6965;i++){
        for(j=0;j<6965;j++){
            sum=b[i]+b[j];
            if(sum==a){
                return TRUE;
            }
        }
    }
    return FALSE;
}

int  sumOfDivisors(int  a){
    int  i,n;
    n=1;
    for(i=2;i<a;i++){
        if(a%i==0){
            n+=i;
        }
    }
    return n;
}

이번에도 1분이 넘긴 했지만...-_-;
아무튼 풀었다.
잔머리 굴리다가 자꾸 틀려서, 그냥 Brutal Force 방식으로 때웠다.

by snowall 2009. 1. 11. 12:32