BOJ : 1929 소수구하기 (파이썬)

소스코드

import sys
import math
n1,n2 = map(int, sys.stdin.readline().split())


for i in range(n1,n2+1) :
    c = 0
    
    for j in range(2, int(math.sqrt(i)) + 1) :
        
        
        if i % j == 0 :
            c+=1
            break
    if c == 0 and i > 1 :
        print(i)
        pass

풀이

앞에 다뤘던 소수문제랑 똑같이 코드를 작성하면 시간초과에 걸리게 됩니다.

그래서 소수일때 다음 수를 나누는것이 아닌 break를 통해 소수가 아니면 바로 다음 수로 넘어가게끔 설계해줍니다.

그 수의 제곱근까지만 소수인지 판별하면 된다는 최적화된 알고리즘을 통해 구현했습니다.

문제

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기