<백준> 1929번 파이썬 알고리즘

실패 코드

import sys
n, m = map(int, sys.stdin.readline().split())
def prime(num):
    
    for j in range(2, num):
        if num % j == 0:
            return False
    return True 

for i in range(n, m+1):
    if prime(i) == True:
        print(i)
    else:
        continue

소수 구하는 부분에서 시간 단축을 시켜줘야 한다

n 의 소수 판별을 위해 2 부터 n-1 까지 반복문을 돌렸는데

그럴 필요 없이 n의 제곱근까지만 돌리면 된다

 

수정 코드 

import sys
import math
n, m = map(int, sys.stdin.readline().split())
def prime(num):
    if num == 1:
        return False
    k  = int(math.sqrt(num))

    for j in range(2, k+1):
        if num % j == 0:
            return False
    return True 

for i in range(n, m+1):
    if prime(i) == True:
        print(i)
    else:
        continue