본문 바로가기

학업 정리

메르센 소수 찾기

 2의 거듭제곱에서 1이 부족한 수를 메르센 수(Mersenne number)라고 한다. 여기서 메르센(Mersenne)은 수학자 마랭 메르센(Marin Mersenne)의 이름이다. 메르센은 저명한 수학자 파스칼의 스승이었다고도 한다. 위키백과

 메르센 수 중에서 소수인 수를 메르센 소수(Mersenne prime)라고 한다. 3, 7, 31, 127 등은 메르센 소수이며, 이같은 소수가 무한히 많은지는 알 수 없다. 그 중 1883년 Ivan M. Pervushin이 발견한 9번째 메르센 소수는 다음과 같다.



이 수가 소수인지 아닌지 모른다고 가정하고, 소수임을 판별하는 알고리즘을 생각해보자.





주어진 수를 N이라 하자.

각 방법의 소요시간은 초당 10^8번의 연산을 기준으로 한 단순 계산이다.



단순한 방법


N을 2부터 N-1까지의 모든 수로 나눠보는 방법이다.

어떤 수로도 나눠지지 않는다면 N은 소수이다.

이 방법은 약 731년이 걸린다.


덜 단순한 방법 1


N을 2부터 sqrt(N)까지의 모든 수로 나눠보는 방법이다.

N이 소수가 아니라고 가정할 때, 자기 자신을 제외하고 가능한 가장 큰 약수가 sqrt(N)이기 때문이다.

이 방법은 약 15초가 걸린다.


덜 단순한 방법 2


덜 단순한 방법 1을 바탕으로 불필요한 연산을 조금 더 줄인 방법이다.

2를 제외한 (혹은 2보다 큰) 모든 소수는 당연하게도 2로 나눠지지 않는다. 즉 주어진 N이 홀수라면 짝수로 나눠볼 필요가 없다.

덜 단순한 방법 1에 비해 연산의 양이 절반으로 줄었다.

이 방법은 약 7.6초가 걸린다.


여전히 느리다. 더 좋은 알고리즘이 반드시 필요하다. 9번째 메르센 소수를 판별하는데 약 7.6초가 걸린다고 계산하면, 단순계산으로 10번째 메르센 소수(2^89-1)는 약 34.5시간이 걸리고 11번째(2^107-1)는 약 2년이 걸린다.


덜 단순한 방법 3


덜 단순한 방법 2를 확장한 방법이다.

덜 단순한 방법 2는 주어진 N이 2로 나눠지지 않는다면 N을 2의 배수로 나누지 않는다. 같은 이유로, 주어진 N이 3으로 나눠지지 않는다면 N을 3의 배수로 나누지 않는다. 따라서 덜 단순한 방법 2에서 나눗셈의 제수(divisor)가 3의 배수면 나눗셈을 진행하지 않고 건너뛴다.

이 방법은 약 5초가 걸린다.


예쁜 방법

덜 단순한 방법 2에서는 N을 2의 배수로 나누지 않고 건너뛴다.

덜 단순한 방법 3에서는 N을 2, 3의 배수로 나누지 않고 건너뛴다.

같은 이유로, 우리는 N을 5, 7, 11, 13, 17, ...의 배수로 나누지 않고 건너뛰어도 된다.

즉, 주어진 N을 sqrt(N) 이하의 소수로만 나눈다.

아주 예쁜 방법은 시간을 크게 단축할 수 있을 것이다. (주어진 N이 크고 나머지 연산이 다른 연산에 비해 비쌀수록 그렇다.)





아래는 덜 단순한 방법 3을 적용한 코드다.



덜 단순한 방법 3으로 과제를 제출했다.