[AP프로그래밍 7월 과제] 문제 설계 및 프로그래밍
1. 문제 설계
다양한 알고리즘을 탐색하고 공부하던 중 유독 소수 판별법이라는 것이 눈에 보여 이를 이용한 문제를 설계해 보면 괜찮을 것 같다고 생각했다.
2. 문제
문제: 소수 판별(ENORMOUS)
정석이의 학원 숙제가 심상치 않다. 도대체 어떻게 하라는 것인지 매우 큰 숫자를 주고 여기서 이 숫자가 소수인지를 판별하라고 한다. 정석이를 도와주도록 하자. 긴 숫자로 이루어진 문자열이 주어지면, 소수라면 prime number, 합성수라면 소인수분해한 후 곱의 꼴로 나타낸다.
입력
정수 n이 입력된다. 소수의 경우 1<n<10^200, 합성수의 경우 1<n<=2147483648
출력
소수라면 “prime number”, 합성수라면, 예를 들어 12면 “2 * 2 * 3”으로 출력한다. 숫자는 오름차순이다.
예제 입력
5400
예제 출력
2 * 2 * 2 * 3 * 3 * 3 * 5 * 5
예제 입력2
2147483647
예제 출력2
prime number
3. 사용한 알고리즘
밀러-라빈 소수 판별법
매우 큰 수에 대해 소수인지를 빠르게 판별하기 위해 밀러-라빈 소수 판별법을 이용한다. 밀러-라빈 소수 판별법은 에라토스테네스의 체보다 훨씬 더 빠르게 특정 수가 소수인지 확률적으로 판별하는 방법이다. 아래에서 밀러-라빈 소수 판별법을 유도해 본다.
증명)
2가지 보조 정리가 필요하다.
[보조 정리 1]-페르마의 소정리
소수 p와 정수 a에 대해서 다음을 만족한다.
a ^p ≡ a(mod p)
a ^(p-1) ≡ 1(mod p) if a % p != 0
위의 정리는 어떤 소수 p와 아무 정수 a를 알 때, a를 p로 나눈 나머지가 0이 아니라면
a를 p번 곱한 수를 소수 p로 나눈 나머지 = a를 소수 p로 나눈 나머지
a를 p-1번 곱한 수를 소수 p로 나눈 나머지 = 1
위 1, 2번이 성립한다는 정리이다.
[보조 정리 2]
소수 p에 대해 x^2 ≡ 1(mod p)이면 x ≡ -1 (mod p) or x ≡ 1 (mod p)이다.
여기서 x^2-1은 p의 배수이므로 이를 인수분해하면 x-1 또는 x+1이 p의 배수가 된다는 뜻이다.
n을 2가 아닌 소수로 가정하면 2가 아닌 소수는 모두 홀수이기 때문에 n-1은 모두 짝수가 되고, 따라서 n-1을 홀수가 될 때까지 2로 나누면 n-1 = d*2^r로 표현할 수 있다. 여기서 n은 소수이므로 양의 정수 a에 대해 페르마의 소정리를 만족, 따라서 a^(n-1) ≡ 1(mod n), n-1에 식을 대입하면 a^(d*2^r) ≡ 1 (mod n), 따라서 (a^(d*2^(r-1)))^2 ≡ 1(mod n)을 만족하고, 여기서 보조 정리 2를 사용하면 (a^(d*2^(r-1))) ≡ -1 (mod n) or (a^(d*2^(r-1))) ≡ 1 (mod n)이 된다. 여기서 다시 2를 밖으로 빼낸 후 보조 정리 2를 다시 사용하면
a^(d*2^(r-2)) ≡ -1 (mod n) or a^(d*2^(r-2)) ≡ 1 (mod n) 가 되고, 이를 보조 정리 2를 사용할 수 없을 때까지 반복하면
a^d ≡-1(mod n) 또는 a^d ≡1(mod n)의 결과가 된다. 이를 통해 n이 소수라면 n보다 작은 양의 정수 a에 대해
a^d ≡1(mod n) 또는 a^(d*2^r) ≡ -1(mod n), 0<=r<=s를 만족한다.
여기서 a가 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41일 때 위 테스트를 모두 통과한다면 n < 3,317,044,064,679,887,385,961,981인 n에 대해 n이 소수인지를 확실하게 판별할 수 있게 되므로 a를 늘려 판별할 수 있는 수의 범위를 확장할 수도 있다.
소인수분해
소인수분해는 위보다 간단한 방법을 이용한다. 1부터 입력받은 수까지 모든 경우를 해 보는 것은 비효율적이다. 약수를 판별할 때 가운데 약수를 기준으로 하여 약수가 대칭적인 형태를 보이는데, 따라서 특정 자연수 N이 소수인지 바로 가운데 약수까지만 나누어떨어지는지 확인하면 된다. 다르게 말해 해당 수의 제곱근까지만 확인하면 된다.
4. 문제 해결 전략
먼저 밀러-라빈 소수 판별법을 코드로 구현하고, 만약 소수라면 prime number를 출력, 소수가 아니라면 소인수분해한 후 각 소인수들의 곱으로 나타내기만 하면 되는 간단한 문제이다. 문제가 된다면 밀러-라빈 판별법을 생각해내는 것인데 나는 그것을 이미 알고 있으므로 간단히 해결할 수 있을 것이다. 소인수분해에 사용되는 제곱근 함수는 파이썬의 math 모듈에서 제공하므로 이를 사용하면 된다.
5. 해결 과정과 시행착오
import mathmath 모듈의 sqrt()를 사용하기 위해 불러온다.
#밀러-라빈 판정
def miller_rabin(n, a):
d = n - 1
while d % 2 == 0:
d //= 2
x = pow(a, d, n)
if x == 1 or x == n-1:
return True
while d != n-1:
x = pow(x,2,n)
d *= 2
if x == 1:
return False
if x == n-1:
return True
return False밀러-라빈 판정법을 코드로 구현하면 위와 같다. 간단히 말해 a^d ≡1(mod n) 또는 a^(d*2^r) ≡ -1(mod n)for some 0<r<s가 성립한다면 소수라는 것을 나타낸 것이다.
def isPrime(n):
if n in
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]:
return True
if n == 1 or n%2 == 0:
return False
for a in
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]:
if not miller_rabin(n,a):
return False
return True밀러-라빈 소수 판별법을 2부터 100까지의 소수에 대해 실행하면 충분히 큰 수에 대해 소수를 판별할 수 있다.
a = int(input())
factors = []
root_a = int(math.sqrt(a))
if isPrime(a):
print("prime number")
else:
d=2
while d <= root_a:
if a % d != 0:
d += 1
else:
factors.append(d)
a//=d
if a > 1:
factors.append(a)만약 입력받은 수가 소수가 아니라면 2부터 그 수의 제곱근까지의 인수로 나눠 보면 된다.
count = len(factors)
if factors:
for i in range(count-1):
print(str(factors[i])+" * ",end="")
print(str(factors[-1]))이후 소인수들을 곱의 꼴로 나타내 출력하면 문제를 해결할 수 있다.
어려움으로는 알고리즘을 코드로 구현하기 전 그 내용을 이해하는 것이 어려웠고, 이후 문제 제작 및 풀이 과정에서는 밀러-라빈 판정법을 코드로 나타내는 데 어려움이 있었다. 테스트케이스로 매우 큰 소수인
531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127를 입력하면 prime number가 출력되는 것을 볼 수 있다.
또 다른 소수로
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151를 입력해도 prime number가 출력되는 것을 볼 수 있으며, 10000000을 입력하면 합성수이므로 소인수분해하여
2 * 2 * 2 * 2 * 2 * 2 * 2 * 5 * 5 * 5 * 5 * 5 * 5 * 5가 출력되는 것을 볼 수 있다.
6. 느낀 점
알고리즘을 정수론적으로 증명하는 것이 새로웠다. 문제 자체가 직관적이고 간단하지만 알고리즘을 알지 못하면 해결하지 못하므로 괜찮은 문제라고 생각한다. 다른 수학적인 알고리즘들도 찾아 증명해 보는 것이 좋을 것 같다.