[Algorithm] 소수(Prime Number) ; 쌍둥이 소수(Twin Primes), 메르센 소수(Mersenne Primes), 골드바흐의 추측(Goldbach's Conjecture)

소수(Prime Number)

약수의 개수를 이용한 소수의 판별

• 1보다 큰 자연수 중에서 1과 자기 자신 이외에는 약수를 가지지 않는 수, 즉 약수의 개수가 2개인 자연수를 소수(Prime Number)라고 한다.

2의 약수 : 1, 2
3의 약수 : 1, 3
4의 약수 : 1, 2, 4
5의 약수 : 1, 5
6의 약수 : 1, 2, 3, 6
7의 약수 : 1, 7

• 2, 3, 5, 7, ... 등은 약수의 개수가 2개 이므로 소수이다.

 

예제

#include <iostream>
using namespace std;

int main() {
    int cnt;
    
    for (int i = 2; i <= 10; i++) {
        cnt = 0;
        for (int j = 1; j <= i; j++) {    // 각각의 i에 대한 약수의 개수 구하기
            if (i % j == 0) {
                cnt++;
            }
        }
        
        if (cnt == 2) {    // 약수의 개수가 2개이면 소수
            cout << i << endl;
        }
    }
}

2
3
5
7

 

쌍둥이 소수(Twin Primes)

• 소수들 중에 3과 5, 11과 13, 17과 19처럼 두 수의 차가 2인 수들이 있다. 이렇게 두 수의 차가 2인 수들을 쌍둥이 소수(Twin Primes)라고 한다.
• 두 수의 차가 1인 소수는 2와 3을 제외하고는 없다.
  • 만약 두 수의 차가 1이라면 두 수는 연달아 있을 것이고, 그렇다면 둘 중 하나는 짝수이기 때문이다.
• 쌍둥이 소수의 전체 개수 구하기는 아직까지 아무도 해결하지 못한 어려운 문제로 남아있다.
• 가장 큰 쌍둥이 소수는 2016년에 발견된 `2996863034895 × 2^{1290000} + 1`과 `2996863034895 × 2^{1290000} - 1` 이다.
• 1994년 미국의 수학자 토마스 나이슬리(Thomas R. Nicely)는 쌍둥이 소수의 역수의 합을 계산하던 중, 인텔 펜티엄 마이크로프로세서 칩이 오류를 일으킴을 발견하였다.
  • 윈도우즈 95 또는 윈도우즈 98 계산기나 마이크로소프트 액셀에서 4195835 × 3145727 ÷ 3145727을 계산했을 때, 4195579가 나온다면 결함이 있는 칩이었다고 한다.
  • 이로 인해서 인텔은 모든 칩을 전량 회수해야만 했다.

 

메르센 소수(Mersenne Primes)

Marin Mersenne (1588-1684)

• 프랑스의 수도사였던 메르센(1588 ~ 1684, Marin Mersenne)은 페르마(Fermat), 갈릴레오(Galileo), 파스칼(Pascal)과 함께 정수론을 발전시켰다.
•  이 때 당시에는 "모든 소수 `p` 에 대해서 `2^{p} - 1` 은 소수이다." 라는 가설이 사실로 받아들여졌다.
  • `2^{2}-1=3, 2^{3}-1=7, 2^{5}-1=31, 2^{7}-1=127` 과 같이 모든 소수 `p` 에 대해서 성립하는 것처럼 보인다.
• 이렇게 사실로 받아들여졌던 가설은 1536년 후댈리쿠스 레기우스(Hudalricus Regius)라는 수학자에 의해 참이 아니라는 사실이 밝혀졌다.
  • `p` 에 `11`을 대입하면 `2^{11}-1=2047` 이라는 값을 얻는데, 2047은 23과 89의 곱으로 표현될 수 있기 때문에 잘못된 가설임을 밝혀내었다.
• 1603년에 피에트로 캐댈리(Pietro Cataldi)는 "`p` 가 `17`과 `19`일 때 `2^{p}-1`이 소수이고, `p`가 23, 29, 31, 37일 때도 소수가 된다."고 주장했으나, 1640년 페르마(Fermat)는 "`p` 가 23과 27인 경우에는 소수가 되지 않는다." 는 것을 알아내었고, 오일러(Euler)가 "`p` 가 29인 경우도 소수가 되지 않는다." 는 것을 밝혀내었다.
• 그래서 메르센(Mersenne)은 `p` 가 어느 값일 때 소수가 되고, 어느 값일 때 소수가 안되는지 밝히고 싶었는데, 1644년 "만약 `p` 가 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 중 하나이면 `2^{p}-1` 은 소수이다." 라고 논문을 발표하였다.
• 하지만 시간이 흘러 후배 수학자들에 의해서 `p` 의 값이 67과 257일 경우에는 소수가 되지 않음을 밝혀지게 되었고, 대신에 61, 89, 107은 포함되어야 함을 알아내었다.
• 메르센은 이 세상의 모든 소수를 `2^{p}-1` 과 같이 간결한 수식으로 표현하고 싶어했다. 후세에 와서 사람들은 평생을 공부와 기도에 바친 메르센에게 다음과 같은 알고리즘을 헌사하였다.
  • "`2^{p}-1` (여기서 `p` 는 소수)의 형태의 수를 메르센 수(Mersenne Number)라고 부르며, `p` 가 소수일 때 `2^{p}-1` 이 소수이면, 그것은 메르센 소수(Mersenne Prime)라 한다."
• 현재 발견한 것 중, 자릿수가 큰 소수들은 대부분은 메르센 소수(Mersenne Prime)가 차지하고 있는데, 메르센 수 중에서 소수가 무한개인지는 아무도 모르기 때문에 당분간 큰 소수를 찾기 위한 경쟁은 메르센 소수에 국한될 것 같다.
• 메르센 소수는 2018년 12월 21일부로 51개가 발견되었다.

 

골드바흐의 추측(Goldbach's Conjecture)

Christian Goldbach (1690-1764)

• 독일의 수학자 골드바흐(1690 ~ 1764, Christian Goldbach)가 당대 최고의 수학자 오일러(1707 ~ 1783)에게 보낸 편지에 다음과 같은 명제가 참인지 거짓인지 증명할 수 있겠느냐고 질문한데서 비롯된 문제이다.
  • "5보다 큰 모든 자연수는 3개의 소수의 합으로 나타낼 수 있다."
  • 예) 6 = 2 + 2 + 2, 7 = 2 + 2 + 3, 10 = 2 + 3 + 5, 20 = 2 + 5 + 13
• 하지만 오일러는 위의 명제를 다음과 같이 바꿔놓았다.
  • "2보다 큰 짝수는 2개의 소수의 합으로 나타낼 수 있다."
  • 예) 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, 20 = 7 + 13
• 하지만 아직까지도 2보다 큰 모든 짝수에 대해서 성립하는지는 250년이 지난 지금에도 해결되지 못하고 있다.

 

소수의 개수

• 1이상 100 이하의 소수는 25개(25%), 1이상 1,000 이하의 소수는 168개(16.8%), 1이상 10,000 이하의 소수는 1,229개(12.3%), 1 이상 100,000 이하의 소수는 9,552개(9.6%), 1 이상 1,000,000 이하의 소수는 78,498개(7.8%)가 있다.
• 지금까지 많은 수학자, 공학자, 과학자들이 더 큰 소수를 찾아내는데 노력하고 있으며, 큰 소수를 찾기 위해서는 더 좋은 컴퓨터 성능이 필요하다.
• 현재까지 발견된 가장 큰 소수는 2018년에 발견된 `2^{82589933}-1` 이다.
  • 51번째 메르센 소수
  • 약 2,233만 자리의 수
• 미국 전기프론티어재단(EFF, Electronic Frontier Foundation)에서는 1,000만 자리가 넘는 소수를 발견하는 사람에게 10만 달러의 상금을 주었으며, 현재는 1억 자리가 넘는 소수를 발견하는 사람에게 15만 달러의 상금을 걸었다.
• 참고 : https://en.wikipedia.org/wiki/Largest_known_prime_number

Largest known prime number - Wikipedia

 

제곱근을 이용한 소수 판별

• 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100이 있으며, 10(100의 제곱근)을 기준으로 서로 대칭됨을 알 수 있다.

100의 약수

 

• 즉, sqrt(100)을 기준으로 100이 1로 나누어 떨어지면 100/1의 몫인 100으로도 나누어 떨어지고, 2로 나누어 떨어지면 100/2의 몫인 50으로도 나누어 떨어지고, 4로 나누어 떨어지면 100/4의 몫인 25로도 나누어 떨어지고, 5로 나누어떨어지면 100/5의 몫인 20으로도 나누어 떨어지고, 10으로 나누어 떨어지면 100/10의 몫인 10으로도 나누어 떨어진다.
• 즉, 어떤 수 `n` 이 소수인지 판별하고자 할 때, 1은 모든 수의 약수이므로 제외하고, 2부터 sqrt(n) 까지의 정수들로 `n` 을 나누어 봤을 때 나누어 떨어지는 수가 없다면 당연히 오른쪽에 대칭되는 수도 존재하지 않기 때문에 `n` 을 소수라고 판별할 수 있다.

 

예제

1이상 10이하의 소수 구하기

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int k, cnt;
    
    for (int i = 2; i <= 10; i++) {
        cnt = 0;
        k = sqrt(i);
        for (int j = 2; j <= k; j++) {
            if (i % j == 0) {
                cnt++;
            }
        }
        
        if (cnt == 0) {
            cout << i << endl;
        }
    }
    
    return 0;
}

2
3
5
7