[백준] 1837

import sys
import math
def checkPrime(n):
    sieve=[True]*n
    a=int(math.sqrt(n))
    for i in range(2,a+1):
        if sieve[i]:
            for j in range(i+i,n,i):
                sieve[j]=False
    return [i for i in range(2,n) if sieve[i]==True]
 
p,k=map(int, sys.stdin.readline().split())
ans=0
tmp=checkPrime(k)
for i in range (len(tmp)):
    if p%tmp[i]==0:
        print("BAD %d"%tmp[i])
        exit()
if ans==0: print("GOOD")

소수(prime number)문제는 단순하게 생각하면 푸는 것 자체는 쉽게 풀리지만

시간이 항상 문제였어서
에라토스테네스의 체 를 이용해서 풀었습니다.