1부터 n 사이에 존재하는 소수를 구하는 알고리즘.
사실 실무에서는 쓰이는 일은 거의 없어요. 만약 있다면 소수 연구하는 수학 학과 뿐이려나.
그러나 알고리즘 관련 문제로서는 약방의 감초처럼 단골이지요.
다들 아시다시피 알고리즘에서 가장 중요한 것은 '속도'에요.
어차피 출력되는 결과는 동일하니 얼마나 빨리 출력하느냐가 판단 기준이 되는 것이지요.
그렇다면 어떻게 코딩해야 가장 좋은 속도를 얻을 수 있을까요?
방법 1.
| Dim i As Long, j As Long For i = 2 To n For j = 2 To i If i = j Then Print i: Exit For If i Mod j = 0 Then Exit For Next j Next i |
2부터 n까지, 그리고 그 사이의 특정값 m에 대하여 2부터 m까지.
중간에 빠져나오는 과정이 없었다면 n(n-1)/2번의 반복이 이루어져요.
가장 많이 쓰이지만, 동시에 가장 느린 방법이에요.
방법 2.
|
Dim i As Long, j As Long If j > Sqr(i) Then Print i Next i |
나누었을 때 0이 나온다는 말은 제값이 피제값의 약수 중 하나라는 뜻이 되지요.
그런데 아시다시피, 약수를 나열하면 원 수의 제곱근을 기준으로 대칭되어 있어요.
다시말해 제곱근 다음의 수들은 검사할 필요가 없다는 뜻이지요.
이로써 1번 방법보다 기하급수적으로 빨라지게 되었어요.
방법 3.
| Dim i As Long, j As Long, num(2 To n) As Boolean For i = LBound(num) To UBound(num) If num(i) = False Then For j = 2 To Int(UBound(num) / i) num(i * j) = True Next j End If Next i For i = LBound(num) To UBound(num) If num(i) = False Then Print i Next i |
에라토스테네스의 체라는 용어를 들어보셨나요?
수들을 마치 체로 걸러내듯, 소수의 배수를 제거해서 남은 것을 취하는 방식이에요.
고구마는 이 알고리즘이야 말로 구현 난이도도 쉽고 속도도 빠르기에 가장 좋다고 생각해요.
위 세가지 방법 외에도 여러가지 방법이 있어요.
현재 가장 빠른 소수 판정 알고리즘으로 밝혀진 것은 'AKS 소수 판정법'이라고 하네요.
이 녀석은 수학적으로 표현하면 간단해보이는데, 코딩해놓으면 분량이 방대해져서 조금 곤란해요. 헤헤.
덧붙여 최근 이런 글을 보았어요.
"VB로는 1초 내로 완료되는 알고리즘을 만들 수 없어요. C 하세요."
틀렸어요.
중요한건 컴파일러의 능력이 아니라 코더의 능력이에요.
보다 나은 방법에 대한 노력은커녕 생각조차 하지 않은 채, 멋대로 언어의 한계를 정의하며 그 무궁무진한 활용성을 통째로 평가절하하는 것. 그것은 무능한 그 자신에대한 자해에 불과해요.
