[백준/python3] 1929. 소수 구하기 (에라토스테네스의 체)

📢 문제 설명

---

문제 자체는 그렇게 어려워보이지 않지만, 이 문제를 통과하기 위해서는 "에라토스테네스의 체" 알고리즘을 알고 있어야한다.

에라토스테네스의 체

[출처] 위키백과, 에라토스테네스의 체

1. 2부터 소수를 구하고 싶은 범위까지의 수를 나열한다.
2. 소수의 배수들을 배열에서 제거한다.

# 위키백과, 에라토스테네스의 체

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

위의 코드는 위키백과에 나오는 python3에서 에라토스테네스의 체를 구현한 코드다.

1. 검색할 전체 수의 개수인 n개의 요소를 모두 True 값으로 만든 배열 sieve를 정의한다.
2. m은 n이하의 최대 소수다. (n까지의 소수들 중 가장 큰 소수)
3. 만약 sieve[i]의 값이 True라면, i는 소수라는 의미로 i의 배수에 해당하는 j에 대해 False로 값을 수정한다. 이에 따라 내부 for문의 시작값은 i+i다! (i, i+1 등으로 하면 안됨!!)
4. 마지막으로 원하는 범위에서 sieve[i]의 값이 True인 i를 출력한다.

---

✏️ 코드 풀이

---

첫 번째 시도 - 시간 초과

m, n = map(int, input().split())
nums = list(set(range(m, n+1)))
for x in nums:
    tmp = nums.index(x)
    for i in range(2,x):
        if x%i == 0:
            nums[tmp] = 1
            break
    if nums[tmp] != 1:
        print(x)

먼저 nums라는 리스트에 m부터 n까지의 값을 정렬한 상태로 저장한다.

그리고 nums의 값들을 하나씩 불러와 각 값에 대하여 소수인지 판별한다. 그리고 만약 소수가 아닌 것이 판별된 경우, 배열의 값을 1로 설정해 

 

---

두 번째 시도 - 에라토스테네스의 체 알고리즘

# 에라토스테네스의 체 알고리즘 공부 선행 필요
m, n = map(int, input().split())

nums = [False]*(2) + [True]*(n-1) # 0,1은 소수X -> 2~n까지 True로 초기화
for i in range(2,n+1):
    if nums[i] == True:
        for j in range(i+i, n+1, i):
            nums[j] = False

for x in range(m, n+1):
    if nums[x] == True:
        print(x)

위의 예제코드와 많이 다르지 않다.

달라진 부분은 0번과 1번의 값을 False로 둔 것인데, 큰 의미는 없다. 검색 시작 값을 2 또는 m으로 설정하면 되기 때문이다. (그래도 좀 더 이해가 쉽도록 False로 초기화했다.) 그리고 범위만 상황에 맞게 바꿨다.

 

이렇게 작성하게 되면 첫 번째 시도에서는 각각의 모든 값에 대해 소수인지 검사해야했던 반면, 이번에는 소수의 배수는 미리 False로 바꿔 배제할 수 있기 때문에 시간 효율성이 높아진다.

성공!