문제
소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때, 10,001 번째의 소수를 구하세요.
풀이
드디어 소수 판별 함수가 등장할 차례이다. 소수의 목록을 구하는 방법에는 크게 두 가지 가 있는데, 하나는 소수판별함수를 작성하여 루프를 돌거나 리스트를 필터링하는 것이고 다른 하나는 에라토스테네스의 체를 이용하는 것이다. 에라토스테네스의 체는 매우 빠르게 동작할 수는 있지만 범위를 알고 있는 경우에 유용할 수 있다.
소수의 분포에는 현재까지는 알려진 규칙이 없으므로 10,001 번째 소수가 어디쯤에 위치할지를 가늠할 수 없다. 따라서 소수 판별 함수를 통해서 2에서부터 소수를 하나씩 세어보는 수 밖에 없을 것 같다.
관건은 얼마나 빠른 소수 판별 함수를 작성할 수 있는가 하는 점이겠다.
소수 판별
소수(Prime Number)는 1과 자기 자신을 제외한 다른 약수를 가지지 않는 수이다. 따라서 2부터 N-1 까지의모든 수로 나눠서 나머지가 항상 0보다 큰지를 검사하면 된다. 가장 간단한 형태는 다음과 같이 만들어진다.
p(n) = begin
for i=2:n-1
n % i == 0 && return false
end
true
end
조금 더 간단하게 만들어보면 다음과 같이 쓸 수도 있다. all() 함수는 Boolean 타입의 연속열을 검사해서 모두 참인지를 검사하는 함수인데, 이를 사용하면 다음과 같이 작성할 수 있다.
p(n) = all(n % i > 0 for i=2:n-1)
이 함수를 이용해서 다음 코드로 답을 구할 수 있다.
let (s, n) = (1, 3)
# 이미 2는 소수이므로 s = 1 부터 시작
while s < 10001
p(n) && (s += 1)
n += 2
end
println(n)
end
보다 빠른 소수 판별 함수
줄리아는 충분히 빠르기 때문에 이렇게 계산해도 1초대에서 답을 구할 수 있다. 하지만 오일러 프로젝트의 다른 문제들에서는 빠른 소수 검사 함수가 필요할 수 있으니, 좀 더 빠른 소수 검사 함수를 만들어보자.
- 2보다 작은 수는 소수가 아니다.
- 2, 3 은 소수이다.
- 2, 3 보다 크면서 2 혹은 3으로 나누어지는 수는 소수가 아니다.
- 3의 규칙에 의해서 2의 배수와 3의 배수(6의 배수)는 모두 건너 뛸 수 있다.
또 어떤 수의 소인수중에서 가장 큰 값은 그 수의 제곱근보다 클 수 없다. 따라서 검사의 범위를 N-1이 아니라 N의 제곱근까지만 검사하도록 한다. 이런 방법을 적용하면 검사의 횟수를 비약적으로 줄일 수 있다.
function isprime(n)
n < 2 && return false
n in (2, 3) && return true
(n % 2 == 0 || n % 3 == 0) && return false
# 5, 7 도 소수
n < 8 && return false
# 이제 5, 7, 9, 11, 13, 15.. 등으로 나눠보면 된다.
# 이 때 3의 배수를 건너뛰는 것이 유리하므로
# 5, 7, _, 11, 13, _, 17, 19, ... 이렇게 나눠본다.
k, l = 5, Int(floor(sqrt(n)))
while k <= l
(n % k == 0 || n % (k+2) == 0) && return false
k += 6
end
return true
end
이 함수를 사용하여 같은 코드로 계산했을 때의 결과는 놀랍게도 4ms 미만의 시간이 걸렸다.