Euler Problem 6

문제는 다음과 같다.

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

문제 그대로 단순하게 알고리즘을 구성하였다. 합계의 제곱과 제곱의 합계를 구한 후, 합계의 제곱에서 제곱의 합계를 뺐다.

' 단순하게 계산하는 방식 (The square of the sum - The sum of the squares)
' {(1 + 2 + ... + 10)^(2)} - {1^(2) + 2^(2) + ... + 10^(2)}
Sub Euler6()
    Const startNum = 1, endNum = 100
    Dim i, sum, SquareOfSum, SumOfSquare
    sum = 0
    ' 합계의 제곱을 구한다
    For i = startNum To endNum
        sum = sum + i
    Next
    SquareOfSum = sum * sum
    ' 제곱의 합계를 구한다
    SumOfSquare = 0
    For i = startNum To endNum
        SumOfSquare = SumOfSquare + (i * i)
    Next
    ' 차이를 보여준다
    MsgBox SquareOfSum - SumOfSquare
End Sub

실행시간(초) : 0

1에서 100까지의 실행시간은 0초로 나왔다. 그래서 1에서 100,000까지 돌려본 결과 실행시간은 0.03125가 나왔다. 매우 빠르게 작동한다.

너무 단순해서 변형하여 보았다. (a+b)^2 - (a^2 + b^2) = 2ab를 응용하여 알고리즘을 구성하여 보았다. 그러면 조금 더 빨라지지 않을까 하는 기대가 있었다. 그러나 결과는 실패였다. 1에서 100까지 약 0초가 걸렸다. 그러나 최대값이 커질 수록 시간이 급증하였다. 1에서 1,000까지는 0.09375초, 1에서 10,000까지는 4.828125초가 나왔다. 100,000까지는 시간이 너무 오래 걸려 테스트를 중단하였다. 그 이유는 정확히 모르겠다. 아마도 중첩 for 문 때문으로 생각된다. 예를 들어 1에서 100까지 계산할 경우, 위 알고리즘은 약 200번(100*2) 계산하는 데, 아래 알고리즘은 약 10,000번(100*100) 계산한다. 아래는 속도면에서 실패한 알고리즘이다.

실행속도에서 실패한 알고리즘

Sub Euler6b()
    Const startNum = 1, endNum = 100
    Dim i, j, result
    result = 0
    For i = startNum To endNum - 1
        For j = i + 1 To endNum
            result = result + (i * j)
        Next
    Next
    result = result * 2
    Debug.Print result
End Sub

실행시간(초) : 0