1929번: 소수 구하기 [Python]

일단 되게는 하자

import math
n, m = map(int, input().split())

for i in range(n, m + 1):
    flag = True
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            flag = False
    if flag:
        print(i)

모든 수를 나누어 보는 것보다 효율적인 sqrt한 값까지 나누어보는 것을 수행하는 방식을 사용하였다.

하지만 시간초과로 나왔고, 원인은 flag를 처리하는데 시간이 소모되었던 것 같다.
그래서 아래와 같이 함수를 정의하여 flag if문 없이 함수의 리턴 값으로 처리해주었더니, 통과되었다.

import math
n, m = map(int, input().split())

def isPrime(i):
    if i == 1:
        return False
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            return False
    return True

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