Euler Problem 5

Euler Problem 5의 문제는 다음과 같다.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

§ evenly divisible : 나누어서 나머지가 없는

이 문제를 처음 보았을 때, 최소공배수를 구하는 문제로 이해했다.

즉 1에서 10까지의 수들의 최소공배수는 2520이다. 그러면 1에서 20까지의 최소공배수는 무엇인가?
최소공배수는 최대공약수를 알면 쉽게 구해진다. 두 수 a, b의 최소공배수는 (a*b)/최대공약수(a,b)이다.
이렇게 두 수의 최소공배수를 구한 후, 그 결과와 그  다음 수의 최소공배수를 구하는 식으로 나가면 20까지의 최소공배수는 구해진다. 즉 2와 3의 최소공배수인 6과 그 다음 수인 4와의 최소공배수를 구해 나가는 것이다.

따라서 최대공약수를 구하는 알고리즘을 만들면 이 문제는 쉽게 해결된다. 최대공약수를 구하는 알고리즘은 유클리드의 알고리즘을 이용하면 된다. 유클리드 알고리즘은 다음과 같다. 두 수 a, b가 있다고 가정하자.

1) a와 b가 같지 않으면 다음을 반복한다.
    2) a > b이면 a = a - b, 그렇지 않으면 b = b - a
3) a(또는 b)가 구하고자 하는 최대공약수이다.

이상과 같은 방식으로 Euler Problem 5를 구한 결과는 다음과 같다.

' Euler Problem 5 (최소공배수 관련 문제)
Sub Euler5()
    Const StartNum = 1
    Const EndNum = 20
    Dim i, j, k
    i = StartNum
    For k = StartNum To EndNum - 1
        j = k + 1
        i = Lcm(i, j)
    Next
    MsgBox i
End Sub

' 최대공약수(유클리디안 알고리즘)
Function Gcd(ByVal i, ByVal j)
    Do While i <> j
        If i > j Then
            i = i - j
        Else
            j = j - i
        End If
    Loop
    Gcd = i
End Function

' 최소공배수(a*b/gcd(a,b))
Function Lcm(ByVal i, ByVal j)
    Lcm = (i * j) / Gcd(i, j)
End Function

실행시간(초):  2.703125

그러나, 위 방식은 최대값이 커짐에 따라 너무 많은 시간이 걸린다. 1에서 20까지 구하는 데 약 2.7초가 걸렸다. 이를 1에서 25초로 확대하였더니 약 99.9초가 걸렸다. 최대공약수를 구하는 유클리디안 알고리즘은 두 수의 차가 너무 크면 시간이 매우 오래 걸린다는 단점이 있다. 따라서 최대공약수 알고리즘을 빼기 방식에서 나머지를 이용하는 방식으로 변형하였다. 그 결과는 아래와 같다.

변형된 알고리즘(나머지 방식)

' Euler Problem 5 (최소공배수 관련 문제)
Sub Euler5()
    Const StartNum = 1
    Const EndNum = 20
    Dim i, j, k
    i = StartNum
    For k = StartNum To EndNum - 1
        j = k + 1
        i = Lcm2(i, j)
    Next
    MsgBox i
End Sub

' 최대공약수2(유클리디안 알고리즘-나머지 이용)
Function Gcd2(ByVal i, ByVal j)
    Dim k
    Do
        k = Mod2(i, j)
        i = j
        j = k
    Loop While k <> 0
    Gcd2 = i
End Function

' 최소공배수2(변형된 Gcd2 이용)
Function Lcm2(ByVal i, ByVal j)
    Lcm2 = (i * j) / Gcd2(i, j)
End Function

' VBA의 Mod함수는 큰 수에 대해 오버플로가 발생. 따라서 나머지를 구하는 함수 따로 작성
Function Mod2(ByVal Num, ByVal Divide)
    Dim Mok
    Mok = Int(Num / Divide)
    Mod2 = Num - (Mok * Divide)
End Function

실행시간(초):  0

위 변형된 알고리즘으로 실행한 결과 20까지는 실행시간이 0초, 25까지도 0초이다. 최대값을 1000으로 하여서야 실행시간이 0.015625초가 걸렸다. 변형되기 전 알고리즘과 비교해보면 너무나 큰 속도차이가 난다. 그러나 수학적 지식이 부족하여 변형된 알고리즘이 무결성을 보장해주는 것에 대해서는 확신이 없다. 10, 20, 25까지는 두 알고리즘 모두 동일한 최소공배수를 나타내 보이는 것으로 보아 그리 큰 문제는 없을 것으로 판단된다. 단, VBA에서 너무 지나치게 큰 수를 입력하면 (예, 1에서 10000), 데이터 허용범위를 넘어가 잘못된 결과값을 산출하는 것 같아(예, 음수), 조심할 필요가 있다.