Bakjoon Q1929 - Python

Q1929

---

Problem

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

Input

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

Output

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

예제 입력

3 16

예제 출력

3
5
7
11
13

나의 제출

a, b = input().split()
a=int(a)
b=int(b)

hint = [False,False] + [True]*(b-1)

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

for k in range(2,a):
    hint[k]=False

for l in range(2,b+1):
    if hint[l]:
        print(l, end='\n')

추가 내용

핵심적인 알고리즘에 대한 설명은 C++ 풀이를 보며 참고하자. 아직 익숙치 않은 python의 문법을 보충하여, 맨 위에서부터 code chunk 별로 설명하겠다.

1. 입력 : a, b를 공백을 통한 구분으로 입력을 받았다. 이때 저장된 a와 b는 string 형태로 저장되어 있기 때문에, int()를 통해 형변환을 시켜주었다.

2. hint array 생성 : python은 아주 elastic한 array forming이 되기 때문에, 맨 앞 두 항이 false(0과 1은 소수가 아니기 때문)이고 나머지 항이 True인 배열은 위 코드처럼 쉽게 만들 수 있다. 최대 판정할 숫자가 b이면, 0부터 시작해야하므로 총 b+1 사이즈의 array가 필요하다.

3. 0, 1을 제외하고 2부터 b+1까지 가는 loop 생성. 처음 2는 일단 소수이고 true로 되어있기 때문에 if 통과. if 안에서 2*2부터 끝까지 2만큼 상승 (즉 4이상의 2배수)하는 수들을 모두 false로 전환. ….무한반복.

4. 2부터 a까지(a이상이므로 a+1이 아니라 a까지만) 모든 value를 false로.

5. print. 매번 repeat할 때마다 끝부분에 개행 삽입.

총평

python으로 하면 훨씬 짧아지긴 하더라. 하지만 그만큼 메모리 사용량도 높고 소요 시간도 크다. 이를 감안하더라도, 엄청난 내부 library의 편의성을 무시할 수는 없을 것 같다.