프로젝트 오일러 007

문제

7번 문제

10001번째의 소수

사이냅소프트

10,001 번째 소수를 구하기 위해서는 2부터 시작해서 소수를 10,000개 찾고 그 다음 번 소수를 찾으면 됩니다. 소수가 배치되는 규칙은 알려져 있지 않기 때문에 범위를 한정할 수 없습니다. (만약 최대 범위를 안다면, 에라토스테네스의 체를 이용해서 "아주 빠르게" 범위 내의 소수를 찾을 수 있습니다.)

사실 (대부분 날려먹었지만) 소수 판별 검사는 워낙 많이 작성했던터라 설명은 좀 미루도록 하겠습니다.

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

def solve():
  # 3부터 시작하고, 2를 카운트에 포함하고 시작하여 홀수만 검사
  n, cnt = 3, 1
  while True:
    if isprime(n):
      cnt += 1
      if cnt == 10001:
        break
    n += 2
  return n


print(solve())

시간 측정하기

파이썬 프로그래머들이 흔히 사용하는 함수 실행 시간 측정 방법으로는 time 모듈을 사용하는 방법이 있습니다.

# utils.py

from time import monotonic
from functools import wraps

def timeit(f):
  @wraps
  def inner(*a, **b):
    c = monotonic()
    r = f(*a, **b)
    print(f"{monotonic() -c :.3f}sec")
    return r
  return inner

@timeit
def somejob():
  pass

이렇게 time 모듈을 사용해서 수행시간을 측정할 수 있고, 예전에는 이러한 방법이 유일한 시간 측정법이었지만, time은 현재 시스템의 상태에 따라 크게 영향을 받고, 엄밀하게 측정하기 어렵다는 문제가 있습니다.

대신, 함수의 수행 시간을 측정하거나 벤치마킹하고 싶다면 timeit 모듈을 사용하는 것도 방법입니다. ipython이나 jupyter를 사용한다면 %time , %%timeit 매직을 사용해서도 1회 시간 측정 및 자동 벤치마크를 간단하게 해 볼 수 있습니다.