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

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

https://www.acmicpc.net/problem/1837

1837번: 암호제작

브론즈 3 (이게 왜 브3??)

수학, 브루트포스, 큰 수 연산

---

접근방법

어떤수를 소인수분해하면 소수들의 곱으로 표현할 수 있다. 그 소수들 중 가장 작은 값이 K보다 작은지에 대한 여부를 확인해야 한다.

 

시행착오가 너무 많았다. p와 q가 소수라는 것 때문에 소인수분해를 하도록 했는데 시간초과가 계속해서 났다.

문제에서 요구하는 것은 입력받은 K값보다 작은 소수라는 것을 유의해야 한다.

소인수분해를 어느 범위까지 할 것인지 고민해야 한다.

 

 

코드 풀이

import sys
P, K = map(int, sys.stdin.readline().split())
flag = False
for d in range(2, K):
    if P % d == 0:
        print(f'BAD {d}')
        flag = True
        break

if flag == False:
    print('GOOD')

 

어떤 값을 소인수분해했을때 얻어지는 값들은 모두 소수이므로, 가장 먼저 구해지는 소수가 K보다 작으면 BAD를 출력하도록 해야한다. 

 

나는 소인수분해의 범위를 어디까지 정해야하는지 몰라서 시간초과가 너무 많이 났다.

그냥 애초에 범위를 K값보다 작게 받아버리면 그 안에서 소수가 나오더라도 K값보다 작은 소수가 나오는 꼴이 되므로 BAD를 출력하고, 거기서 소수가 나오지 않으면 굳이 더 연산을 하지않고 GOOD을 출력하도록 한다.

 

BAD는 해당 소수를 출력해야하지만 GOOD은 그럴 필요가 없기 때문에 K값 이상의 연산을 할 필요가 없었다.