Euler Problem 9

Euler Problem 9는 다음과 같다.

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

이 문제는 a+b+c=1000, a<b<c, a² + b² = c² , a=b=c=자연수 라는 점을 이용하여 순차적으로 계산하면 그 답을 구할 수 있다. 아래 알고리즘은 그 솔루션이다.

Option Explicit
Sub euler9()
    Dim a, b, c, Sum, aLimit, bLimit
    Sum = 1000
    ' a+b+c=sum, a>b>c 이기 때문에, 최소한 a+(a+1)+(a+2)=sum. 따라서 a=(sum-3)/3을 초과 못함
    aLimit = Int((Sum - 3) / 3)
    For a = 3 To aLimit     ' a는 3이상부터 시작된다.
        bLimit = Int((Sum - a) / 2)    ' b는 a보다 크고 c보다 작아야 하기 때문에
        For b = a + 1 To bLimit
            c = Sum - a - b
            If c > b Then
                If (c * c) = (a * a) + (b * b) Then
                    Debug.Print a, b, c, a * b * c
                End If
            End If
        Next
    Next
End Sub

실행시간(초):  0.078125

그러나, 위 방식은 Sum의 값이 커짐에 따라 매우 느려진다. 중첩 for 문이고, 순차적으로 계산하기 때문이다. Sum의 값을 10,000으로 하였더니 실행시간이  3.46875초가 되었고, 다시 100,000으로 올렸더니 336.25초가 나왔다(답도 2세트가 나옴). 아무래도 문제가 있는 알고리즘인 것 같다. 어떻게 하면 반복계산을 줄일 수 있을까?