백준 알고리즘 1837번 암호제작(python)

단순 수학 문제이다. 2061 좋은 암호와 똑같은 문제 같다.

마찬가지로 에라토스테네스의 체를 사용하면 쉽게 풀 수 있다.

P, 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 = [i for i in range(2, K) if li[i] == 1]

good, bad = 1, 0
for n in prime:
    if P%n == 0:
        good, bad = 0, n
        break
print("GOOD" if good else f"BAD {bad}")