소수 소수

http://www.mersenne.org 홈페이지를 방문해 보면 특이한 공지사항(?)이 하나 있다.

On December 15, 2005, Dr. Curtis Cooper and Dr. Steven Boone, professors at Central Missouri State University, discovered the 43rd Mersenne Prime, 2^30,402,457-1. The CMSU team is the most prolific contributor to the GIMPS project. The discovery is the largest known prime number.

대충 해석해 보면 작년 가을쯤에 미주리 주립대학교의 두 교수가 43번째 메르센 소수를 발견했다는 소식이다.

2^30,402,457-1 란 숫자를 10진수로 나열하면 무려 9,152,052 개나 된다고 한다. 이 수가 진짜 메르센 소수인지 검증하기 위해 5일동안 16 개의 Itanium2 1.5 GHz CPUs 를 사용했다고 하니 참말로 열정이 대단하다.

흠... 메르센 소수? 도대체 뭘까? 궁금증을 참지 못하고 구글신에게 물어보았다.

링크 참조 : http://ko.wikipedia.org/wiki/%EB%A9%94%EB%A5%B4%EC%84%BC_%EC%86%8C%EC%88%98

요약해 보면, n 이 소수일때 2^n -1 도 소수이면 해당 n은 메르센 소수가 된다는 것이다. 이걸 뒤집에 생각하면 2^n -1 이 소수가 아닐때도 있다는 것이다. 해당 값이 소수인지 어떡해 검사할까?

소수는 1과 자기 자신 이외에 나누어 지지 않는 수라는건 익히 알고있다. 간단히 생각나는데로 구현해 보면...

bool isPrimaryNumber(unsigned int n)
{
for (unsigned int i =2; i< n; ++i)
{
if (0 == (n%i) )
return false;
}
return true;
}

가 되지 않을까? 아니면 지금 까지 알려진 소수들을 인터넷 검색을 해서 구해온 후 몇번의 루프를 돌면 되지 않을까? unsigned int 면 통상 2^32 -1 이 최대값인데 그보다 큰 녀석들은?
어 그러고 보니 2^x -1 은 다들 소수인거 같네(메르센 소수는 아니지만) ? 정말 ?...

소수 하면 생각나는 영화가 있다.
바로 조디 포스터 주연의 Contact ... (이후 스포조심^^)
베가 행성에서 보내온 정체불명의 전파속에 숨은 과학의 언어 '소수'

1963년 미국 일리노이 대학에서는 23번째 메르센 소수를 발견하였는데 이를 기념하기 위하여 ‘211213-1은 소수이다’라고 새긴 우편 스탬프를 찍어 냈다고 한다. -
여러분들도 GIMPS 프로젝트에 일원이 되어 자신만의 역사적인 우표를 만드는 날이 오길 ^^..