백준 알고리즘 2061번 좋은 암호(python)

소수 관련 문제는 항상 시간싸움인 것 같다. 에라토스테네스의 체는 알고 있으면 매우 편리한 것 같다.

L, K = map(int, input().split())
li = [1]*K
for i in range(2, int(K**0.5)+1):
    if li[i] == 1:
        for j in range(i+i, K, i):
            li[j] = 0
prime_li = [i for i in range(2, K) if li[i] == 1]

good = 1
for n in prime_li:
    if L%n == 0:
        print(f"BAD {n}")
        good = 0
        break
if good == 1:
    print("GOOD")