프로젝트 오일러 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

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의 배수를 불필요하게 재검사하지 않게합니다.

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

어쨌든 이 방법으로 계속 모든 수를 검사하면 됩니다. 저는 여기서 2는 찾았다고 가정한 상태에서 홀수만 검사했지만, 홀수 중에서 3의 배수도 피하는 방식등 시행횟수를 더 줄여보면 전체 시간을 더 단축할 수 있습니다.

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


if __name__ == '__main__':
    main()

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


if __name__ == '__main__':
    main()