Site icon Wireframe

오일러 프로젝트 07

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, … 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요.(http://euler.synap.co.kr/prob_detail.php?id=7)

접근

소수판별함수를 만들어볼 차례이다. 사실 이 블로그를 통틀어서 여러 번 소개한 적이 있다.

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
  if n < 9:
    return True
  k, l = 5, int(n ** 0.5 + 1.5)
  while k < l:
    if n % k == 0 or n % (k + 2) == 0:
      return False
    k += 6
  return True

소수를 판별하기 위해서는 기본적으로 2, 3, … n – 1 까지의 수를 모두 나눠보아야 한다. 하지만 만약 n이 소수가 아니라면 n = p * q 로 표현할 수 있을 것이며, p <= q 라면 2 에서부터 n의 제곱근 사이에 p가 등장해야 한다. 따라서 n의 제곱근 이하에서만 검사를하면 검사 횟수를 크게 줄여서 속도를 높일 수 있다.

def main():
  a, b = 3, 1  # 2는 소수이므로 카운트에 미리 포함시킨다.
  while b < 10001
    if isprime(a):
      b += 1
    a += 2
  print(a)


# 시간 측정을 위해서는 ipython이나 jupyter 에서 실행한다.
%time main()
# 104745
# CPU times: total: 0 ns
# Wall time: 38.5 ms

참고로 특정한 범위 내에서의 소수들을 골라내려면 소수 판별 함수를 사용하는 것보다 에라토스테네스의 체를 사용하는 것이 더 빠르다. (물론 리스트를 사용해서 필터링해야 하기 때문에 메모리는 더 많이 사용해야 한다.) 다만 이 문제는 10,001번째 소수가 어디쯤 위치하는지 알지 못하는 상태에서 풀어야하기 때문에 소수 판별 함수를 사용해야 한다.

Exit mobile version