소수 계량 함수(素數計量函數, 영어: prime-counting function)는 주어진 양의 실수 $x$에 대해 그 값보다 작거나 같은 소수의 개수를 세는 함수이다. 일반적으로 그리스 소문자 $\pi$를 사용하여 $\pi(x)$로 표기하지만, 원주율 $\pi$와는 직접적인 관계가 없다.
정의
$\pi(x)$는 $x$ 이하의 소수의 개수로 정의된다. 예를 들어, 10 이하의 소수는 2, 3, 5, 7로 총 4개이므로 $\pi(10) = 4$이다. $n$번째 소수 $p_n$에 대하여 $\pi(p_n) = n$이 성립한다. 소수의 특성상 일반항을 대수적으로 전개할 수 없기 때문에 초월함수에 속하며, 연속함수가 아니므로 미분 불가능하지만 증가함수이므로 적분은 가능하다.
소수 정리
소수 계량 함수의 점근적 거동을 설명하는 정리가 소수 정리(prime number theorem)이다. 18세기 말 카를 프리드리히 가우스와 아드리앵마리 르장드르는 $\pi(x)$가 $x / \ln x$에 근접함을 추측하였고, 이는 1896년 자크 아다마르와 샤를장 드 라 발레푸생이 각각 독립적으로 리만 제타 함수의 성질을 이용하여 증명하였다. 소수 정리는 다음과 같이 표현된다.
$$ \lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1 $$
이와 동치로서 로그 적분 함수 $\operatorname{li}(x)$를 사용한 표현 $\displaystyle \lim_{x \to \infty} \frac{\pi(x)}{\operatorname{li}(x)} = 1$도 널리 사용된다.
명시적 공식
소수 계량 함수는 폰 망골트 명시적 공식(von Mangoldt explicit formula)을 따른다. 이 공식은 베른하르트 리만이 1859년에 발표한 논문에서 제시되었으며, 엄밀한 증명은 1895년 폰 망골트에 의해서 이루어졌다. 이 공식은 리만 제타 함수의 비자명 영점들의 정보를 포함하며, $\pi(x)$를 로그 적분 함수와 제타 함수의 영점들로부터 오는 주기적인 진동 항의 합으로 표현한다.
관련 함수
소수 계량 함수는 체비쇼프 함수 $\theta(x)$와 $\psi(x)$, 리만 제타 함수 $\zeta(s)$ 등 여러 중요한 수론적 함수와 밀접하게 연결되어 있다. 특히 리만 가설은 $\pi(x)$의 오차 항에 대한 가장 강력한 가능한 한계를 제공하는 문제로, 소수 계량 함수의 연구와 깊이 연관되어 있다.
수치적 계산
$\pi(x)$의 정확한 값을 계산하는 알고리즘으로는 Lucy-Hedgehog 알고리즘, Meissel-Lehmer 알고리즘, LMO(Lagarias-Miller-Odlyzko) 알고리즘 등이 개발되어 있으며, $x$의 범위에 따라 $O(n^{2/3})$ 또는 $O(n^{3/4})$의 시간 복잡도로 계산이 가능하다.
