1929: 소수 구하기 - Python

문제

https://www.acmicpc.net/problem/1929

풀이 1 (오답)

M, N = map(int, input().split())

for num in range(M, N+1):
    is_prime = True
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            is_prime = False
            break
    if is_prime:
        print(num)

• num == 1일 때를 처리하지 못한다.
• 시간도 굉장히 오래 걸린다.

풀이 2 (에라토스테네스의 체)

M, N = map(int, input().split())
a = [False, False] + [True] * (N-1)
primes = []
for i in range(2, N+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i, N+1, i):
            a[j] = False

for p in primes:
    if p >= M:
        print(p)

• 효율적인 소수 찾기 알고리즘인 "에라토스테네스의 체"를 사용하였다.
• 다만 M 이상의 수를 출력하는 좋은 방법이 떠오르지 않아 if문을 사용한 것이 아쉽다.

풀이 3 (뚝딱이 공학도님 풀이)

M, N = map(int, input().split())
for num in range(M, N+1):
    if num == 1:
        continue
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            break
    else:
        print(num)

• 시간이 오래 걸리긴 하지만 훨씬 간단하다.
• 풀이 1에서 num == 1일 때를 처리했고, is_prime 대신 for-else문을 사용하였다.

---

오늘의 교훈

• 소수를 구할 때는 에라토스테네스의 체 알고리즘을 사용하자.
• for-else, while-else문을 잘 사용해보자.
  • for, while문에서 break로 인해 반복문이 중단되지 않았을 때만 else문이 실행된다.
  • else문은 "반복이 끝까지 정상적으로 마무리되었다"라는 의미로 전체 순회를 완료한 경우에 실행된다.

참고 자료

• 2. 소수 구하기 - 에라토스테네스의 체
• [백준] 1929번 : 소수 구하기 (파이썬)