파이썬 알고리즘 106 번 | [백준 1929번] 소수 구하기

106. 소수 구하기

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

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

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

예제 입력 1
3 16
예제 출력 1
3
5
7
11
13

1) 어떤 전략(알고리즘)으로 해결?

• 에라스토테네스체 사용할 것

2) 코딩 설명

<내 풀이>

m,n=map(int, input().split())
arr = [0]*(n+1)
arr[1]=1
for i in range(2,n+1) :
    if arr[i] ==0 :
        for j in range(2*i,n+1,i) : 
            arr[j]=1 #소수는 체크
for i in range(m,n+1) :
    if arr[i] ==0  :
        print(i)

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

• 내 틀린 풀이
• 인덱스 1 에 1 채워넣지 않았움

m,n=map(int, input().split())
arr = [0]*(n+1)

for i in range(2,n+1) :
    if arr[i] ==0 :
        for j in range(2*i,n+1,i) : 
            arr[j]=1 #소수는 체크
for i in range(m,n+1) :
    if arr[i] ==0  :
        print(i)

<반성 점>

• 자꾸 에라스토테네스로 문제 풀 때 배열 인덱스 1에 1 미리 채워넣는 것을 까먹는다.
  꼭 1은 소수가 아니므로 미리 1을 넣어주도록 하자