동백 // 백준 파이썬 1929번 소수 구하기

반응형

​

소수 구하기

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	121092	33925	24001	27.127%

문제

---

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

---

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

---

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

---

3 16

예제 출력 1

---

3 5 7 11 13

내 코드

 

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

r = N + 100

# 반복문 range만큼 리스트를 False로 가득 채움
check = [False for _ in range(r)]


# 에라토스테네스의 체를 사용하여 소수를 구해놓기

# 2부터 ~ 범위(r)의 제곱근까지
for i in range(2, int(r**0.8)): 
    # 만약 check[i]가 False면 
    if check[i] == False:
        # 소수에 해당하지 않는 부분은 True로 체크해줌
        # ex) 4, 6, 8 etc....

        # i의 2배수부터, 3배수, 4배수
        for j in range(2 * i, r , i):
            check[j] = True


ans = []

for i in range(M, N + 1):
    #만약 i가 2보다 크거나 같으면(1은 소수가 아니기에)
    if i >= 2:
        # 만약 check[i]가 False라면, 즉 소수라면
        if check[i] == False:
            ans.append(i)

# ans 크기별로 정렬
ans.sort()
for _ in ans:
    print(_)