[SW Expert Academy] 3131. 100만 이하의 모든 소수 파이썬 정답 코드

SW Expert Academy

---

수정 전과 후 버전이 있습니다. 아래쪽이 수정 후 버전으로, 최종 정답 코드입니다!

 

1. 수정 전 접근 방식

• 1,000,000이라는 큰 수

n이 소수인지 판별하는 가장 간단한 함수(아래 is_prime 메서드)로는 절대 문제를 해결하지 못한다. 따라서 더욱 효율적인 소수 판정법을 고민해야 했다.

• 에레토스테네스의 체

내가 기존에 알고 있는 소수 판정법은 2부터 루트 n까지의 소수로 나누어 보는 것이었다. 그러나 이 문제는 n이 1부터 100만까지이기 때문에 ① 2부터 루트 n까지의 '소수'들을 구하고 ② 그 소수들로 n을 나누는 과정에서 시간 초과가 날 것이 뻔했다. 따라서 결국... 소수 판정법을 알아내기 위해 소수 나무위키 페이지를 읽어보았다. 그렇게 발견한 것이 바로 '에레토스테네스의 체'이다.

에레토스테네스의 체를 간단히 말하면, 1 ~ 100까지의 소수를 모두 찾을 때 루트 100보다 작은 소수들(2, 3, 5, 7)의 배수를 제외하는 것이다. 단, 1은 소수가 아니므로 처음에 제외하고, 각 2, 3, 5, 7처럼 소수 그 자체는 제외하지 않는다.

다시 이 문제로 돌아와서 루트 1,000,000 이하인 소수를 구하고, 2 ~ 1,000,000에서 각 소수의 배수를 제거하는 방식으로 코드를 작성해야겠다고 생각했다.

 

 

2. 수정 후 파이썬 코드

• filter( ) 내장 메서드: 현재 코드에서 설명하자면, 컬렉션( [2, 3, ... 999, 1000] )의 각 요소를 is_prime( ) 메서드에 대입하여 반환값이 True일 때만 새로운 리스트의 요소로 포함한다.

import math

def is_prime(n):
    flag = True
    for i in range(2, n):
        if n % i == 0:
            flag = False
            break
    return flag

# 루트 1,000,000 이하인 소수 찾기
n = int(math.sqrt(1000000)) # n == 1,000
primes_under_n = list(filter(is_prime, [x for x in range(2, n + 1)]))

# 1,000,000 이하인 소수 찾기
primes = {x for x in range(2, 1000000)}
for i in primes_under_n:
    # primes에서 루트 1,000,000 이하인 소수의 배수를 제거
    primes = primes - {i * x for x in range(2, 1000000//i + 1)}

# 출력
for x in sorted(list(primes)):
    print(x, end=' ')

 

 

3. 기타

루트 100만 이하인 소수를 찾을 때도 다시 또 루트 1,000 → 루트 (루트 1,000) ... 이런 식으로 에라토스테네스의 체를 반복 사용해야 할까 고민했다. 그러나 구현이 너무 복잡해질 것 같았고 1,000 정도는 반복문으로 소수를 판정해도 시간 초과가 나지 않을 것이라 판단하여 is_prime( ) 메서드를 사용했다.

 

그런데 다른 분들이 제출한 답안은 메모리가 약 7만kb이고 실행 시간이 250 ~ 300ms인데 반해 내 코드는 메모리가 약 20만kb이고 실행 시간도 2,212ms이다. ...최적화가 시급하다. 어떻게 실행 시간을 줄일 수 있을까?

 

 

---

4. 수정 후 접근 방식

솔직히 말하면 아무리 고민해 보아도 기존에 작성한 코드를 어떻게 바꾸어야 할지 감이 잡히지 않았다. 따라서 검색해 보았고, 길이가 100만 + 1인 불리언 리스트를 생성하는 것에 힌트를 얻었다. 정말 신기하게도 불리언 리스트를 생성하는 것을 보자마자 다음 코드는 어떻게 작성해야 하는지 바로 알겠더라.

 

• 인덱스를 숫자처럼 처리한다.

예를 들어 인덱스 2는 숫자 2인 것이다. 따라서 2를 제외한 2의 배수를 모두 제거한다는 건 결국 불리언 리스트에서 인덱스 4, 6, 8...의 값을 False로 바꾸는 것이다.

 

• 4는 2의 배수이므로, 모든 4의 배수는 결국 2의 배수이다.

이 부분이 바로 아주 매력적인 논리(?)라고 생각된다. 2의 배수를 체크했다면, 인덱스 4는 이미 False이고 4의 배수도 모두 False이다. 즉, Fasle인 인덱스는 검사할 필요가 없으니 반복문을 continue한다.

 

 

5. 수정 후 정답 코드

import math

n = 1000000

numbers = [True] * (n + 1)
numbers[0] = False # 인덱스 0은 없는 취급
numbers[1] = False # 1은 소수가 아니다.

for i in range(2, int(math.sqrt(n))):
    if not numbers[i]:
        continue

    for j in range(i * 2, n + 1, i): # i * 2함으로써 소수 자체 (2, 3...)등 제외하지 않음
        numbers[j] = False

for index, value in enumerate(numbers):
    if value:
        print(index, end=' ')