[백준] 1929번 소수 구하기(Python - 파이썬)

백준 1929번 문제입니다. (solved.ac)기준 실버 2 문제입니다.

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

M과 N이 주어지고 M과 N사이의 소수들을 한 줄에 하나씩 증가하는 순서대로 출력하면 되는 문제입니다.

문제 접근

처음에는 단순히 범위 내의 '모든' 수들을 1과 자기 자신이외의 '모든' 수들로 나눠가며 소수판별을 했었는데 그랬더니 시간초과 오류가 발생하였습니다. 약간의 검색을 통하여 2를 제외한 모든 짝수는 소수가 아니라는 사실과 소수를 판별할 때 1과 자기 자신을 제외한 '모든' 수가 아닌 제곱근까지만 나누어도 된다는 사실을 알게되어 그 것을 이용하여 코드를 수정하였습니다. (2를 제외한 짝수는 건너 뛰기 / 2부터 자기자신의 제곱근 까지 나누어봄) 

 1은 합성수도 소수도 아니기 때문에 m(소수를 찾을 범위에서 시작값)이 1 이라면 m += 1을 해주어 2부터 탐색이 가능하도록 하였습니다.

정답 코드

import sys
m, n = map(int, sys.stdin.readline().rstrip().split())

# 소수인 값들을 넣을 리스트(정답)
prime = []

# 1은 소수가 아님
if m == 1 : m += 1

for i in range(m, n+1) :

    # 2는 유일하게 짝수 중에서 소수
    # 2일 경우를 제외하고 모든 짝수에서는 소수판별을 하지 않음
    if i != 2 and i % 2 == 0 :
        continue

    # 우선 prime 리스트에 넣어놓고 소수판별 후 소수가 맞다면 유지 아니라면
    # prime리스트에서 제거할 것임.
    prime.append(i)

    for j in range(2, int(i** 0.5)+1) :
        # 만약 1과 자기 자신 이외의 수로 나누어진다면 소수가 아니므로
        # prime 리스트에서 제거
        if i % j == 0 :
            del prime[-1]
            break

# 소수들 한 줄에 하나씩 순차적으로 출력
for i in prime :
    print(i)