Euler Problem 10

문제

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

소수를 구하는 문제이다. 에라토스테네스의 체를 이용하면 빠르게 계산이 가능하다. 그러나 VBA에서는 배열의 크기가 long의 크기(2,147,483,647)를 넘어가면 안되기 때문에 매우 큰 수를 사용하기에는 어려움이 있다. 물론 그 전에 메모리 한계 때문에 에러가 발생하기도 한다. 다행이 이 문제는 그 크기 한계가 2,000,000개이다. 그래서 배열 사용이 가능하여 에라토스테네스의 체를 이용하여 알고리즘을 구현하였다.

에라토스테네스 체의 알고리즘

① 2부터 N까지의 수를 배열에 지정한다. (여기서 N = 2,000,000 이다)
② 2를 제외한 2의 배수 모두를 제거한다. (즉 소수가 아닌 것으로 표시한다)
③ 그 다음 작은 소수인 3을 제외한 3의 배수 모두를 제거한다.
④ 그 다음 작은 소수인 5를 제외한 5의 배수 모두를 제거한다.
⑤ 이런식으로 계속해서 그 다음 작은 소수가 sqrt(N)이 될 때가지 반복한다.
⑥ 제거되지 않고 남은 수가 모두 소수이다.

Sub Euler10()
    Const Num = 2000000
    Dim Prime(2 To Num) As Byte
    Dim i, j, Limit, Sum
    For i = 2 To Num
        Prime(i) = 1
    Next
    Limit = Int(Sqr(Num))
    For i = 2 To Limit
        If Prime(i) = 1 Then
            For j = i * 2 To Num Step i
                Prime(j) = 0
            Next
        End If
    Next
    Sum = 0
    For i = 2 To Num
        If Prime(i) = 1 Then
            Sum = Sum + i
        End If
    Next
    Debug.Print "2에서 " & Num & " 사이의 소수 합: ", Sum
End Sub

실행시간(초):  0.71875