🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]1929번 - 소수 구하기

1929번 - 소수 구하기

문제

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

입력

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

출력

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

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

해결할 방법을 생각해보자.💡

이 문제는 소수를 찾는 방법 중 정말 효율적인 에라토스체네스의 체를 사용해야하는 문제다.

내가 이전에 풀어왔던 소수찾기 방법을 사용하면 이중반복문 때문에 시간 초과에 걸린다…

그래서 검색을 통해 에라토스체네스의 체가 무엇인지를 보았다.

https://blog.naver.com/mmdm1989/221486521909

내용을 요약하자면 1부터 100까지의 수가 있을 때, 소수가 아닌 1부터 지운 후 2의 배수를 지워준다.

그리고 다음에 3의 배수를 지워주고, 4는 2의 배수에서 지워졌기 때문에 다음은 5로, 5의 배수를 지워준다.

이런 식으로 100까지 수를 지워주다 보면 소수들만 남게된다는 원리다.

이것을 이용하기 위해서는 Boolean 자료형을 이용하고, 반복문 range의 범위를 잘 이용해야한다.

최소, 최대 값을 받아주자.

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

에라토스의 체를 사용할 변수를 만들어주자. 인덱싱을 사용하면 접근하는 시간을 최소화할 수 있다고 한다.

그래서 불리언 자료형을 사용해서 최대값 만큼 길이의 불리언 리스트를 만들어주자. 인덱스는 0부터 시작하기 때문에 최대값에 1추가한 길이만큼 만들어주자.

eratos = [True] * (N+1)

인덱싱을 사용할 때, 0과 1은 소수가 아니므로 False로 미리 지정해주자.

eratos[0] = False
eratos[1] = False

이제 그 길이만큼 반복문을 사용해서, 만약 인덱스를 해서 True라면 그 수에서 2배한 값부터 최대값 까지 그 수 만큼 건너뛰며 False로 바꿔주자.

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

그러면 이제 소수인 인덱스에 해당하는 요소만 True로 남아있을 것이다.

예제와 같이 3 16을 입력받으면 다음과 같이 나온다.

image

이제 최소, 최대값의 길이만큼 반복문을 사용해서, 해당 인덱스가 참이라면 그 값을 출력해주면 끝이다.

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

코드💻

M, N = map(int, input().split())
eratos = [True] * (N+1)
eratos[0]  = False
eratos[1]  = False
for i in range(N+1):
    if eratos[i]:
        for j in range(i*2, N+1, i):
            eratos[j] = False

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

해결 로그

문제 푼 날짜 체크
2022-06-12 ✔
   
   
   
   

2022

[web]jQuery 복습 3

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

13 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

14 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

5 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

10 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑