베르트랑 공준(Bertrand's Postulate)은 수학의 한 정리로, 3보다 큰 모든 자연수 n에 대해 n과 2n−2 사이에는 반드시 소수 p가 하나 이상 존재한다는 내용입니다. 이 명제는 1845년 프랑스 수학자 조제프 베르트랑(Joseph Bertrand)이 실험적 데이터를 바탕으로 처음 제안했으며, 이후 1852년 러시아의 수학자 파프누티 체비쇼프(Pafnuty Chebyshev)가 수학적으로 증명하였습니다.
베르트랑 공준의 공식
n < p < 2n − 2
여기서 n은 n > 3을 만족하는 자연수이며, p는 그 사이에 존재하는 소수를 의미합니다.
소수(Prime Number)란 1과 자기 자신만을 약수로 가지는 수를 뜻합니다. 예를 들어 2, 3, 5, 7, 11 등이 소수에 해당합니다.
실제 응용에서는 아래와 같이 조금 더 완화된 형태의 표현이 널리 사용됩니다.
n < p < 2n (모든 n > 1)
즉, 1보다 큰 임의의 수 n에 대해서도 n보다 크고 2n보다 작은 소수가 항상 존재한다는 의미입니다.
예제
입력
5
출력
7
설명
입력값이 5일 때, 5부터 2×5=10 사이의 범위에서 소수를 찾으면 7이 해당됩니다.
입력
11
출력
13, 17, 19
설명
입력값이 11일 때, 11부터 2×11=22 사이의 범위에서 소수는 13, 17, 19 세 개입니다.
베르트랑 공준을 활용한 소수 찾기 C++ 프로그램
아래 프로그램은 주어진 수 n에 대해 n+1부터 2n−2까지의 범위를 탐색하면서 각 수가 소수인지 검사하고, 소수인 경우만 화면에 출력합니다. 소수 판별은 2부터 √n까지의 수로 차례대로 나누어 나머지가 0이 되는 값이 있는지 확인하는 방식으로 구현되었습니다.
예제 코드
#include <iostream>
using namespace std;
void printPrime(int n) {
int flag = 0;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) // i가 n의 약수인 경우
flag++;
if(flag == 0)
cout<<n<<" ";
}
int main() {
int n = 22;
cout<<"범위 ("<<n<<", "<<2*n<<") 내의 소수 :\t";
for (int p = n + 1; p < 2 * n - 2; p++)
printPrime(p);
return 0;
}
실행 결과
범위 (22, 44) 내의 소수 : 23 29 31 37 41
실행 결과를 보면 22와 44 사이에서 23, 29, 31, 37, 41이라는 다섯 개의 소수가 발견되었습니다. 이처럼 어떤 수 n을 선택하더라도 n과 2n 사이에 반드시 소수가 존재한다는 점을 직접 확인할 수 있으며, 이것이 바로 베르트랑 공준이 실제로 성립함을 보여주는 좋은 예입니다.