(Python) 백준 1929번 - 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

풀이

저번에 풀이했던 1978번과 같은 방식인 에라토스테네스의 체로 풀이를 했다. 다만 2부터 (자기 자신 - 1)을 모두 나눠보면 시간 초과가 발생하여 어떻게 해야 하는지 고민하던 중,  2부터  √자기자신 까지만 나눠도 된다는 사실을 알게 되어 그렇게 풀이해 보니 제한 시간 내에 통과할 수 있었다.

import sys
import math

n, m = map(int, sys.stdin.readline().split())
for i in range(n, m+1):
    if i == 1: # 1은 소수가 아님
        continue
    else:
        flag = True # 일단 모든 수가 소수라고 가정하고
        for j in range(2, int(math.sqrt(i))+1): # 2부터 sqrt(자기자신)까지 
            if i % j == 0: # 한 번이라도 나누어 떨어지면
                flag = False  # 소수가 아님
                break
        if flag: # 소수만 출력
            print(i)