[알고리즘][Python] 백준(BOJ) 1837 암호제작_파이썬

 

1837 암호제작    www.acmicpc.net/problem/1837

1837번: 암호제작

 

 

문제 풀기 전 공부할 것 : 큰 수 연산

 

 

 

 

 

 

 

풀이

<내용>

• k보다 작은 소수로 p가 나누어 떨어지면 좋지 않은 암호이기 때문에 k보다 작은 소수들을 찾아야 한다.
• k보다 작은 소수를 찾았다면 각각의 소수로 p를 나눌 수 있는지 확인하고 그 결과를 출력하면 된다.

 

 

<코드>

p, k = map(int, input().split())

prime = [False, False] + [True] * (k-2)
for i in range(2, int(k**0.5)+1):
    if prime[i]:
        for j in range(i+i, k, i):
            if prime[j]:
                prime[j] = False
                
flag = True
for i in range(2, k):
    if prime[i]:
        if p % i == 0:
            flag = False
            break
            
if flag:
    print('GOOD')
else:
    print('BAD', i)