프로젝트 오일러 010

문제

10번 문제

이백만 이하 소수의 합

사이냅소프트

이전 문제에서 소개한 소수 판별 함수가 성능이 쓸만하기 때문에 소수 판별함수를 써서 풀 수도 있는 문제입니다. 단, 여러분의 PC 사양이 제법 좋은 편이라면 말이죠.

def isprime(n):
  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

print(sum(x for x in range(200_0000) if isprime(x)))

아 그런데, 마지막 코드를 보면 이런 생각이 듭니다. 2를 제외하면 짝수를 검사할 필요가 없으니, range(3, 200_0000, 2) 를 범위로 사용하면 루프를 절반으로 줄일 수 있으니까 시간을 절반으로 줄일 수 있겠네?

사실 이 부분은 큰 차이는 없습니다. 거의 모든 짝수가 초반에 False로 걸러지는 대다가, 리스트 축약 문법은 for 루프가 아니기 때문에 오버헤드가 크지 않기 때문입니다. (7~8% 정도의 속도향상은 있습니다.)

에라토스테네스의 체

이 문제는 소수의 범위를 결정해서 알려줍니다. 즉 특정한 범위 내의 소수를 모두 찾는 문제입니다. 이 때에는 에라토스테네스의 체를 만드는 것이 가장 빠른 방법입니다. 에라토스테네스의 체를 '빠릿'하게 만들 때 주의점은 for 루프를 최소화한다는 것. 발견된 소수의 배수들을 삭제할 때에는 리스트의 슬라이싱 문법을 사용하는 것이 가장 빠릅니다.

def sieve(n: int) -> list[int]:
  s = [1] * (n + 1)
  s[:2] = [0, 0]   # 0, 1은 소수아님
  for i in range(2, int(n ** 0.5 + 1.5)):
    if s[i]:
      s[2*i::i] = [0] * ((n - i) // i)
  return [i for (i, x) in enumerate(s) if x]

print(sum(seive(200_0000)))