[Project Euler] 23. 두 초과수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?

23. 두 초과수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다.
또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다.
따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다.
두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?

Click

초과수를 구할 때마다 이전에 구한 초과수들과 더해가며 초과수들의 조합으로 만들어진 수들에 표시를 함.

<script>
//약수들의 합
function sumOfDivisior(n){
    var sum = 1;
    for(var i=2; i<=n/i; i++)
        if(n%i == 0)
            sum += i + (((n/i))==i?0:(n/i));
    return sum;
}
//두 초과수의 조합으로 만들어 지지 않는 수들의 합.
function p023(n){
    var max = (28123>n)?28123:n;
    
    var nums = new Array(); //숫자가 두개의 초과수의 합으로 표현 되는지를 판단.
    var abundant = new Array(); //초과수들을 저장할 배열.
    var cnt = 0;        //초과수를 count.
    
    var sum = 0;
    for(var i=1; i<max; i++){
        if(sumOfDivisior(i) > i){            
            abundant[cnt++] = i;
            for(var j=0; j<cnt; j++)
                if(i+abundant[j] < max)
                    nums[i+abundant[j]] = false;
        }
        if(nums[i] != false)
            sum += i;
    }
    return sum;
}
</script>