백준 1837번 / 암호제작 / 파이썬 (브루트포스 알고리즘 / 큰 수 연산)

📚문제

출처 : 백준 1837번 (https://www.acmicpc.net/problem/1837)

 

📝풀이

정답율이 20%대여서 살짝 긴장했다

 

다행히 문제를 보니까 그렇게 어렵진 않은데

(P가 두 소수의 곱이므로 약수를 구하면 1과 자기 자신을 제외한 p,q 가 나온다)

P의 범위가 10의 100승이라 매우 큰 숫자를 연산해야한다

하나하나 다 보기엔 시간이 매우 오래걸린다

이걸 푸는게 관건이다

 

 

K보다 작은 모든 수들중에서 소수에 해당하는 숫자로

P가 나누어 떨어진다면 

문제에서 얘기하는 Bad Case(=좋지 않은 암호) 이다

그런 경우만 보면 되는것이다

# 1837번 암호제작
P, K = map(int,input().split())

for i in range(2,K): # K보다 작아야 하므로 +1을 하지 않아도 된다
    if P % i==0:
        print(f'BAD {i}')
        break
else:
    print('GOOD')

 

앞으로도 이렇게 큰 수 연산하는 문제는 

큰 수에 대해 반복문 할 생각하지말고 조금 더 생각의 전환을 시도해보자