[백준/파이썬]1837번 암호제작

-코드

from math import sqrt
p, k = map(int, input().split())
sieve = [True] * k
flag = True
for i in range(2, int(sqrt(k)) + 1):
    if sieve[i]:
        for j in range(i + i, k, i):
            sieve[j] = False
arr = [i for i in range(2, k) if sieve[i]]
for i in arr:
    if p % i == 0:
        flag = False
        break
if flag:
    print("GOOD")
else:
    print("BAD", i)

예전에 못풀었던 문제였으나 소수를 for로 구하여 해결을 하려 했으나 범위가 너무 넓어서 시간 초과가 생겨서 찾아보니 에라토스테네스의 체를 사용하면 된다고하여 코딩을 하는 중 추가로 p를 가준으로 하여 풀면 시간 초과가 난다는 것을 알고 기준을 k로 두고 k보다 작은 소수로 나눠지면 flag를 통해 출력이 되도록하고 에라토스테네스의 체의 기본 코드는 K번째 소수라는 문제를 참고하여 풀었습니다.