프로젝트 오일러 007

10,001번째 소수

소수가 분포한 규칙은 현재까지는 알려져 있지 않기 때문에 범위를 한정할 수는 없고, 10,001번째 소수를 찾을 때까지 전수검사가 필요합니다. 따라서 루프의 횟수를 줄이고, 효율적인 소수 판정 함수를 개발해야 합니다.

def isprime(n: int) -> bool:
	if n < 2:
		return False
	if n < 4:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	k, l = 5, n ** 0.5 + 1
	while k < l
		if n % k == 0 or n % (k + 2) == 0:
			return False
		k += 6
	return True

• 실제로 어떤 자연수 N은 높은 확률로 2나 3의 배수입니다.
• 곱해서 N이 되는 인수들의 짝은 N의 제곱근을 중심으로 분포합니다. 따라서 나눗셈 검사는 N의 제곱근까지만 합니다.
• 5부터 시작하여 5, 7, 11, 13, .. 과 같이 +2, +4의 간격으로 증가하여 3의 배수를 불필요하게 재검사하지 않게합니다.

이 세 가지 아이디어를 반영하면 비록 파이썬이지만 제법 효율적인 소수 찾기 함수를 만들 수 있습니다.

def main():
    i, j = 1, 1
    while i < 10001:
        j += 2
        if isprime(j):
            i += 1
    print(j)


if __name__ == '__main__':
    main()

Julia

Julia에서도 동일한 방식으로 함수를 구현해도 좋습니다만, Primes라는 모듈에 이미 훌륭한 소수 검사 함수가 구현되어 있습니다.

function isprime(n::Integer)::Bool
	n < 2 && return false
	n < 4 && return true
	(n % 2 == 0 || n % 3 == 0) && return false
	n < 10 && return true
	k, l = 5, Integer(floor(sqrt(n) + 1.5))
	while k < l
		(n % k == 0 || n % (k + 2) == 0) && return false
		k += 6
	end
	true
end

그래서 그냥 잘 만들어진 함수를 가져다 쓰기만 하면 됩니다. 게다가 빠르죠.

using Primes

@time let (i, j) = (1, 1)
	while i < 10001
		j += 2
		isprime(j) && (i += 1)
	end
	println(j)
end