백준 python 문제 - 소수 구하기(1929)

백준 문제 - 소수 구하기(1929)

 

[문제 간단 설명]

M과 N 사이의 수 중에서 소수만을 골라 순서대로 출력하는 것이다.

 

[문제 풀이 핵심]

1. 두 숫자의 사이의 범위를 지정해야 한다.

2. 소수를 구해서 순서대로 출력해야 한다.

3. 백만 단위의 큰 숫자가 나오므로 프로그램 작동 과정이 간결해야한다.

 

[문제 풀이 과정]

1. 에라토스테네스의 체의 원리를 이용한다. 에라토스테네스의 체란 2부터 시작해서 각각 숫자의 배수를 지워나가는 과정을 의미힌다. 이 과정을 사용하면 하나하나 숫자를 확인하는 것보다 작동 시간을 획기적으로 줄일 수 있다.

 

[소스 코드]

import sys

M, N = map(int, sys.stdin.readline().split())
demicial_list = [False, False] + [True]*(N-1)
new_N = int(N ** 0.5)

for i in range(2, new_N+1):
    if demicial_list[i] == True:
        for j in range(2*i,N+1,i):
            demicial_list[j] = False
for i in range(M, N+1):
    if demicial_list[i] == True:
        print(i)

 

[작동 원리]

1. M, N에서 스페이스바를 기준으로 두 정수를 입력 받는다.

2. 소수를 판별하는 리스트를 제작하고, 0과 1를 제외한 소수를 입력 할 수 있도록 제작한다.

3. 처음부터 시작해서 만약 값이 True라면 그 값을 제외한 나머지 배수를 전부 False로 바꾼다.

4. 수의 제곱근까지만 계산하여 시간을 단축하고, 그곳까지만 하면 모든 배수는 걸러지게 된다. ( 제곱근 이상의 숫자를 2배하면 N의 범위를 초과하게 된다,)

5. 완성된 리스트에서 True 값만 따로 범위에 맞추어 출력한다.