아주 큰 소수를 찾아라

컴퓨터를 이용하여 97이 소수인지 합성수인지를 알아내기 위해서 다음 그림과 같은 순서도를 이용할 수 있다.

그러나 아주 큰 자연수 N이 소수인지를 알아내기 위해 이와 같은 알고리즘을 이용하면 컴퓨터를 이용하더라도 많은 시간이 걸린다. 하지만, 컴퓨터에 소수 2, 3, 5, 7, 11, … 등의 목록을 저장해 두고 있다면, 다음과 같은 수학적 사실을 이용하여 계산 시간을 크게 단축시킬 수 있다.

"자연수 N이 이하의 모든 소수로 나누어 떨어지지 않으면 N은 소수이다."

예를 들어, 이므로 9 이하의 소수 2, 3, 5, 7만 생각하면 된다. 즉, 97은 2, 3, 5, 7로 모두 나누어 떨어지지 않으므로 97은 소수이다. 이와 같은 방법으로 100 이하의 소수 2, 3, 5, …, 97만으로 10000 이하의 모든 자연수에 대하여 그 수가 소수인지의 여부를 가릴 수 있다.

한편, 2008년 9월에 미국 UCLA의 수학자들이 컴퓨터 75대를 네트워크로 연결하여 현재까지 알려진 소수 중 가장 큰 수인 을 발표하였고, 다른 연산 방식을 사용하는 컴퓨터를 이용하여 이 수가 소수임을 검증하였다고 한다. 이 수는 약 1300만 자리의 소수로서, 숫자 하나의 폭을 1mm씩 하여 모든 숫자를 나열하면 그 길이가 약 13km에 달할 뿐 아니라, 개인용 컴퓨터를 이용하여 소수인지를 알아내려면 수천 년이 걸린다고 한다. 이들은 '전자 개척 재단(Electronic Frontier Foundation)'에서 1천만 이상 자리의 소수를 발견하는 사람에게 주기로 한 10만 달러의 상금을 받게 되었다.

- 출처 : <연합뉴스 (2008년 9월)>