[프로젝트 오일러] 문제7 - 10001번째 소수

문제

영문

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

바로가기

 

한글

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.

이 때 10,001번째의 소수를 구하세요.

바로가기

 

해설

파이썬 (Python) + 수학적 해석

방법 1

소수란 1또는 자기 자신으로밖에 나누어 떨어지지 않는 수를 뜻합니다. 그러니 자기 자신보다 작거나 같은 수로 모두 나눠본 다음, 자기 자신으로밖에 나누어지지 않는다면 그 수는 소수입니다!

 

prime_th = 0
n = 1

while prime_th<10001:
  n += 1
  x = 2
  while x<n:
    if n%x == 0:
      break
    x += 1

  if x == n:
    prime_th += 1
  
print(n)

위 아이디어를 통해 반복문으로 자기보다 작은 수로 모두 나누기 시도를 하는 코드입니다. 하지만 이 방법은 굉장히 느립니다. \

 

방법 2

def isPrime(n):
  if n in (2,3):
    return True
  elif not n%6 in (1,5):
    return False

  div_check = 5 #6k + 5 꼴부터 시작
  sqrt_n = int(n**(1/2))
  
  while div_check <= sqrt_n: # 제곱근 이하의 수만 탐색
    if n%div_check == 0: #6k + 5꼴
      return False
    div_check += 2
    
    if n%div_check == 0: #6k + 1꼴
      return False
    div_check += 4

  return True

이제 방법 1에서 계산 횟수를 줄여봅시다.

 

우선 첫 번째로 나누어 떨어지는지 탐색시 제곱근 이하의 수만 탐색해주어도 됩니다. 왜냐하면 어떤 수가 제곱근 이하의 수로 나누어 떨어지지 않는다면, 그 이상의 수로도 나누어 떨어지지 않을 테니까요.

 

(이는 귀납법으로 간단하게 증명 가능합니다. 어떤 수가 제곱근 이상의 수로 나누어 떨어진다면, 원래 수를 그 수로 나누면 몫은 제곱근 이하가 될 것입니다. 하지만 제곱근 이하의 수로 나누어 떨어지지 않는다 가정했으면 이는 모순입니다.) 

 

두 번째로는 6으로 나눈 나머지가 1이거나 5인 수만 탐색해주어도 됩니다. 왜냐하면 다른 경우의 수는 모두 2 또는 3으로 나누어지는 경우니까요.

 

prime_th = 2
target_th = 10001
n = 5 #2,3은 소수인지 아니까 5부터 시작
# 이후 계속 6k+5, 6k+1꼴을 탐색
answer = 0

while answer == 0:
  # 6k+5
  if isPrime(n):
    prime_th += 1
    if prime_th == target_th:
      answer = n
  n += 2
  # 6k+1
  if isPrime(n):
    prime_th += 1
    if prime_th == target_th:
      answer = n
  n += 4

print(answer)

이후 다음과 같이 비슷하게 6k+5 또는 6k+1 꼴인 숫자만을 탐색해주시면 됩니다.

 

방법 3

target_th = 10001
n = 5
prime_list = [2,3]
is_add2 = True # 2와 4를 번갈아서 더하는 역할

while len(prime_list) < target_th:
  sqrt_n = int(n**(1/2))
  prime_i = 0 # prime_list에서 쓰는 index
  is_prime = True
  
  while prime_list[prime_i] <= sqrt_n:
    if n%prime_list[prime_i] == 0:
      is_prime = False
      break
    prime_i += 1

  if is_prime:
    prime_list.append(n)

  if is_add2: #6k+5꼴 일때는 2 더하기
    n += 2
    is_add2 = False
  else: #6k+1꼴 일때는 4 더하기
    n += 4
    is_add2 = True

print(prime_list[-1])

 소수 목록을 리스트에 저장해 두고, 리스트에 있는 소수로만 나누어보고 판별하는 법도 있습니다! 나누기를 좀 더 적게 시도할 수 있다는 장점이 있지만, 메모리를 많이 차지한다는 단점이 있습니다.

 

(추가로 코드가 반복되는게 싫어 2와 4를 더해주는 부분은 플립플롭?식으로 만들어봤습니다)

 

C

#include<stdio.h>
int main(void) {
	int ptest=2, pcount=0;
	long ncount = 1;
	while (pcount < 10001) {
		ncount++;
		ptest = 2;
		while (ptest <= ncount) {
			if (ncount%ptest == 0) {
				if (ncount == ptest) {
					pcount++;
				}
				break;
			}
			ptest++;
		}
	}
	printf("%ld", ncount);
}

방법 1을 구현한 코드입니다. C라서 그런지 빠르게 결과가 나오네요. 

 

정답

104743