[백준] 1929번 파이썬 (소수 구하기)

1. 문제와 예제

문제

예제

---

2. 전체 코드

import sys
input = sys.stdin.readline

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

# M부터 N까지 확인
for i in range(M, N+1):
    if i == 1: # 1은 소수가 아니므로 제외
        continue
    for j in range(2, int(i**0.5)+1): # 2부터 루트i까지 (그 이상은 확인할 필요 없음)
        if i % j == 0: # 소수가 아님
            break
    else: # for문에 대한 else (for문이 다 돌 때까지 해결되지 않았음을 의미)
        print(i)

---

3. 풀이

처음에는 for문에서 2부터 루트i까지 대입해서 찾는 방법을 몰라서 2부터 i까지 대입해서 찾으려 했다. 그랬더니 시간 초과 오류가 나서 내가 수학적으로 모르는 게 있겠다 싶어 검색해서 해결하였다. '에라토스테네스의 체'라고도 하는, 소수를 구별해낼 때 효율적인 방식을 사용해야 한다. 이는 시간 복잡도를 O(n) -> O(n^(1/2))로 줄여준다고 하니 알아두자.