BOJ 1929 소수 구하기 Python3

문제 출처 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

import math
a,b = map(int,input().split())
for b in range(a,b + 1):
    if b == 1:
        continue
    if b == 2:
        print(b)
    else:
        boolT = True
        for c in range(2,int(math.sqrt(b)) + 1): # 제곱근을 통해서 나누어지는 수 검사를 줄인다. 왜냐? 수가 많아질수록 for문이 도는 속도는 더 길어지기 때문
            if b % c == 0:
                boolT = False
                break
            else:
                continue
        if boolT == True:
            print(b)
        else:
            continue

시간 복잡도를 약간 고려해 주어야 하는 문제이다. 앞의 1978문제와 비슷하다. 기존과 동일하게 1과 자기자신 숫자 사이의 수들로 나누어 보는 방법이 있긴하지만, 좀더 빠르게 하기 위해서 제곱근 + 1 한 값에 대해서 검사를 해주었다