소수의 개수

#소수(Prime Number)?

1과 자신의 수로만 나눠지는 수를 소수(素數)라고 하고, 영어로는 Prime Number라고 불린다. 소수가 아닌 수를 합성수라고 하는데 모든 합성수는 소수들의 곱으로 나타낼 수 있고, 이를 소인수분해(Prime Factorization)라고 한다. 다항식을 인수분해하여 단순화 시키면 그 해를 쉽게 구할 수있는 것처럼, 임의의 수의 소인수분해하는 것을 매우 중요하다.

고대 그리스 시대에서 부터 소수의 중요성은 인정되었고, 소수를 구하는 법은 에라토스테네스의 체(Sieve of Eratosthenes)라고 알려져있고, 유클리드는 소수의 개수는 무한하다고 증명하였다.

[소수의 무한성 증명하기]

소수의 개수가 유한하다고 가정하고 그 개수가 k개라고 하자. 그러면 그 모든 소수의 곱으로 된 수보다 1이 큰 자연수 N을 생각할 수 있다.

이 수가 새로운 소수임을 이제 추론해 보자. N은 기존의 각 소수 p로 나누면 나머지가 1이다. 따라서 1과 자신 이외의 약수가 없으로 소수이다. 이 N은 기존의 r개의 약수와 같지 않으므로 새로운 소수이다. 모순이다. 결론적으로 소수의 개수는 유한하지 않다.

#소수의 개수

x보다 작거나 같은 소수의 개수를 나타내는 함수를 일반적으로 pi(x)라고 하는데, 이것이 어떤 형태를 가질 것인가가 예전부터 있어 왔던 중요한 질문이었다.

아직까지는 어떤 수식으로도 나타낼 수 없지만, 아래 그래프에 1부터 100까지의 값을 나타내었다.

더 큰 x에 대해서도 구할 수있는데, 백억까지 나타내보면 아래 그래프와 같다. 숫자가 커서 로그 스케일로 나타내었는데, 놀랍게도 거의 직선으로 나타난다.

좀 더 자세히 보기 위해, 숫자가 크니 소수의 밀도를 구해보자.

1798년에 르장드르(Legendre)가 근사적으로 아래와 같이 구했고,

러시아 수학자 파프누티 체비쇼프(1821~1894)는 다음을 증명하였다고 한다.(내용 이해를 못해 자세한 것은 생략)

위의 소수에 관한 내용은 여기를 참고했음. How many primes are there?