백준_No1837_암호제작

문제

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하여야 한다.

입력

암호 P(4 ≤ P ≤ 10100)와 K (2 ≤ K ≤ 106) 이 주어진다.

출력

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

---

풀이

해당 문제를 풀기 위해는 해결해야 할 점이 몇가지 있다.

• 소수를 어떻게 판단할 것인가?
• 암호 P의 약수 중 소수로 이뤄진것은 무엇인가?

위의 문제부터 천천히 해결해보자.

 

소수를 어떻게 판단할 것인가?

어떤 수의 소수의 여부를 확인 할 때는 약수의 성질을 이용하여 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.

 

예를 들어 12의 약수는 1,2,3,4,6,12 이다.

이는 다음과 같이 앞뒤로 짝을 지을 수 있다.

1 * 12 = 12

2 * 6 = 12

3 * 4 = 12

4 * 3 = 12

6 * 2 = 12

12 * 1 = 12

 

이를 보면 약수들이 대칭적으로 짝을 이루는 것을 알 수 있다. 그렇기에 1과 자기자신을 제외한 약수가 존재하는지 확인하기 위해선 자기자신의 제곱근(루트)까지만 확인하면 된다.

12의 경우 12의 제곱근. 즉, 2 √3 까지만 확인하면된다.

다만 한 두 개의 소수를 판별하는 것이 아니라 대량의 소수를 한꺼번에 판별하고자 할 때 사용하는 것은 에라토테네스의 체이다.

 

에라토스테네스의 체

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 이에 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

1. 2 ~ 120까지의 모든 숫자를 나열한다.
2. 2는 소수이므로 Primae numbers에 2를 넣고 2의 배수들을 모두 지운다.(빨간 색)
3. 남아있는 숫자에서 가장 작은 숫자. 즉, 3은 소수이므로 오른쪽에 3을 넣고 3의 배수들을 모두 지운다.(초록색)
4. 남아있는 숫자에서 가장 작은 숫자. 즉, 5는 소수이므로 오른쪽에 5을 넣고 5의 배수들을 모두 지운다.(초록색)
5. 위의 과정을 반복한다.

이 과정을 python코드로 작성하면 다음과 같다.

sieve = [True] * n

m = int(n**0.5)
for i in range(2,m+1):
	if sieve[i]:
            for j in range(i*2,n,i):
                sieve[j] = False
 
 prime_numbers = [i for i in range(2,n) if sieve[i] == True]

 

 

암호 P의 약수 중 소수로 이뤄진것은 무엇인가?

위의 소수문제가 해결이 되면 쉬워진다.

나온 소수 중 입력 받은 암호 P와 딱 나눠 떨어지는 소수가 있다면 K이하의 소수와 곱을 한것이기에 실패를, 없다면 K이하의 소수와 곱을 하지 않은것이기에 성공이다.

 

이를 합해서 코드로 작성을 하면 다음과 같다.

 

P, K = map(int, input().split())

sieve = [True] * K

for i in range(2, int(K**0.5)+1):
    if sieve[i]:
        for j in range(i*2, K, i):
            sieve[j] = False

prime_numbers = [i for i in range(2, K) if sieve[i] == True]

good, bad = True, 0

for i in prime_numbers:
    if P % i == 0:
        good, bad = False, i
        break
        
print("GOOD" if good else "BAD {0}".format(bad))

 

[참고]

https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

https://coding-factory.tistory.com/600

https://jinho-study.tistory.com/640