[백준] 1929번: 소수 구하기 (python)

1929번: 소수 구하기

---

문제)

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

 

입력 :

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

 

출력 :

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

 

 

풀이)

처음에 푼 풀이. 문제를 보자마자 에라토스테네스의 체가 생각나서 구글링을 해보았고,

https://ko.wikipedia.org/wiki/에라토스테네스의_체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

를 기반으로 코드를 만들어 보았다. 다음은 그렇게 만들어진 코드이다.

 

import sys
n, m = map(int, sys.stdin.readline().split(" "))
 
li = []
for i in range(n, m+1):
    li.append(i)
 
for i in li:
    if i == 1:
        pass
    elif i != 2 and i % 2 == 0:
        pass
    elif i != 3 and i % 3 == 0:
        pass
    elif i != 5 and i % 5 == 0:
        pass
    elif i != 7 and i % 7 == 0:
        pass
    else:
        print(i)

 

https://www.acmicpc.net/board/view/39203

글 읽기 - ★☆★☆★ [필독] 소수 구하기 FAQ ★☆★☆★

나무위키의 에라토스테네스의 체에 대한 설명 중 일부

 

 

n, m = map(int, input().split(" ")) # 입력 받기
sieve = [True] * (m+1) #1 부터 m+1까지의 True로 이루어진 리스트
# m+1을 사용하는 이유는 문제에서 m 이하라고 했기 때문.
 
o = int((m+1) ** 0.5) #(m+1) ** 0.5까지의 수만 확인하면 됨.
for i in range(2, o + 1): # 2부터 확인 시작
    if sieve[i] == True:
        for j in range(i+i, m+1, i): #예를 들어 3일때, 6부터 3의 배수를 제거
            sieve[j] = False
 
for i in range(n, m+1): #Ture값의 인덱스로 출력함.
    if sieve[i] == True and i != 1:
        print(i)

 

 

---

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

1929번: 소수 구하기