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

문제

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

 

입력

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

 

출력

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

 

정답

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

number = [True for i in range(N+1)]

for i in range(2, int(N**0.5)+1):
    if number[i]:
        for j in range(2*i, N+1, i):
            number[j] = False

for index in range(M, N+1):
    if number[index] and index!=1:
        print(index)

---

전에 풀어보았던 셀프 넘버의 문제와 형식이 유사하다.

2021.03.09 - [🔍알고리즘/백준] - [백준/python] 4673번 : 셀프 넘버

[백준/python] 4673번 : 셀프 넘버

문제에서는 M부터 N까지의 수 중 소수를 구하지만

배열의 index를 사용할 것이기 때문에 N+1까지의 True가 들어간 배열을 만든다.

💥 여기서 N+1까지의 배열을 만드는 이유는 0부터 시작하기 때문이다.

이제 여기서 소수가 아닌 수들을 False로 바꿔주어

마지막에는 M부터 N+1번째 배열 중 값이 True인 배열만 출력해주면 된다.

💥 여기서 중요한 점은 1은 소수가 아니기때문에 제외해주어야 한다는 점이다. (index != 1)

 

소수를 구하는 방법은 에라토스테네스의 체 개념을 이용하는데

이 개념에 대해서는 아래의 포스팅에서 자세히 다루어보았다. 

2021.03.10 - [🔍알고리즘/🔅개념정리] - 에라토스테네스의 체

[파이썬/python] 에라토스테네스의 체