230207 [1929 : 더 빠르게 소수 구하기]

앞의 문제와 비슷하게 for문 두개를 사용해서 풀면 시간초과가 뜬다

‘에라토스테네스의 체’를 이용해서 코드를 작성해야 한다.

시간을 줄이기 위해 2부터 i까지 다 검사하는 것이라 아니라, 2부터 i의 제곱근(루트)까지만 검사하면 된다.

 

import sys

N, M = map(int, sys.stdin.readline().rstrip().split())

prime_num = []

for i in range(N, M+1):
    flag = 0
    if i == 1 : continue # 1은 소수가 X
    
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            flag = 1
            break
            
    if flag == 0:
        prime_num.append(i)

print(*prime_num, sep='\\n')