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

문제 요약 및 풀이

M이상 N이하의 소수를 모두 출력

 

이 문제 같은 경우 1부터 ~ 1,000,000까지 소수인지 아닌지 일일이 검사한다면 시간 초과가 걸리게 될 것이다.

그렇기에 에라토스테네스의 체라는 알고리즘을 쓸 예정이다. 밑의 gif 파일을 보자.

에라토스테네스의 체

이 gif 파일을 보면 2부터 120사이의 소수를 구하는데 2의 배수, 3의 배수... N의 배수를 검사하는 것을 볼 수 있다.

해당 배수들을 제거하게 되면 소수를 찾을 수 있다.  '에라토스테네스의 체'의 시간복잡도는 O(Nlog(logN))이다.

 

일단 M과 N의 제한은 (1 ≤ M ≤ N ≤ 1,000,000) 이기 때문에 1부터 1,000,000까지의 소수를 미리 구해놓고 M과 N사이의 소수를 반환시켜줄 것이다. N의 배수를 제거해야 되기 때문에 bool타입의 b배열을 생성해주고 소수는 2부터 시작하기 때문에 0, 1 부분을 False로 초기화해준다. 또한 소수를 저장해야 하기 때문에 배열 sosu를 생성해준다.

# 0, 1 = False, 소수는 2부터 시작, 배열의 index : 0 ~ 999999
a = 1000000
sosu = []
b = [False, False] + [True] * (a - 1)

 

배수를 지우거나 건너뛰어야 하기 때문에 아래의 코드와 같이 만들어준다.

for i in range(2, a + 1):
    if b[i]:
        sosu.append(i)
    for j in range(2 * i, a + 1, i):
        b[j] = False

간단하게 설명을 하자면 b배열에는 b[0], b[1]을 뺀 b[2] ~ b[999999] 까지 True로 초기화가 되어있다.

'2' 자신은 소수이기 때문에 배열 sosu에 추가를 해주고 2의 배수는 False로 바꿔준다. 이렇게 해주면 2의 배수 중 2 자신만 빼놓고 나머지는 False로 되어서 일일이 소수인지 판별을 안 해줘도 False로 되어있는 부분은 건너뛰고 True일 때만 소수를 구하게 된다. 이해가 안 되면 해보면 된다. 

 

완성된 코드!! 👍😊

a = 1000000
b = [False, False] + [True] * (a - 1)
sosu = []
for i in range(2, a + 1):
    if b[i]:
        sosu.append(i)
    for j in range(2 * i, a + 1, i):
        b[j] = False

M, N = map(int, input().split())
for i in sosu:
    if M <= i <= N:
        print(i)