백준 알고리즘 1929번: 소수 구하기 (Python)

문제 정보

---

 

1929번: 소수 구하기

 

 

핵심

---

앞서 설명한 에라토스테네스의 체를 활용하여 문제를 풀이해야 함

해당 글은 아래 참고 링크를 확인하면 될것 같다

 

풀이

---

from sys import stdin
M, N = map(int, stdin.readline().split())
prime = [True for _ in range(N+1)]
prime[0], prime[1] = False, False
for i in range(2, int(N**0.5)+1):
    if prime[i]:
        j = 2
        while i*j<=N:
            prime[i*j] = False
            j += 1

for i in range(M, N+1):
    if prime[i]:
        print(i)

 

동일하게 에라토스테네스의 체를 사용하여 주어진 구간의 소수를 출력해주었다!

M이상 N이하이므로 구간이 N을 포함하도록 하는것을 실수하지 말아야 한다!

 

참고

---

GitHub - dduneon/CodingTestPy

 

백준 알고리즘: 1978번 소수 찾기