====== 소수 (Prime number) ======

===== 관련된 성질들 =====

  * 유클리드의 정리 ([[wp>Euclid's theorem]]) 
    * 소수의 갯수는 무한히 많다
  * 소수정리 ([[wp>Prime number theorem]]) 
    * n이하의 소수의 개수는 대략 n/ln(n)개이다. 바꿔쓰면, n번째 소수의 값은 대략 n*ln(n)이다 
    * 실제 백만(10^6) 이하 소수의 개수는 약 8만개. 10억(10^9) 이하 소수의 갯수는 약 5천만개. ([[https://en.wikipedia.org/wiki/Prime-counting_function#Table_of_%CF%80(x),_x_/_log_x,_and_li(x)|링크]])
  * n번째 소수 p_n의 더 타이트한 upper/lower bound는 n(log(nlogn)-1) < p_n < nlog(nlogn) 이다
    * https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities
  * 메르텐스의 제 2정리 ([[wp>Mertens' theorems]])
    * n이하 소수들의 역수의 합은 O(lnln(n))
  * n이하 자연수의 소인수의 개수의 평균은 O(logn)
  * 소수 간극 ([[wp>Prime gap]]) - 연속된 두 소수의 차
    * 이론상 상한은 없지만, 2^64 이하 범위에서는 소수 간극이 1550 이하이다. 2^32 이하 범위에서는 464 이하.
    * 이로부터 n에서 가장 가까운 소수를 찾기 위해서는, 그냥 최대 O(464)개의 수에 대해서 소수여부를 확인하면 된다는 것을 알수 있다.
  * 베르트랑 공준 ([[wp>Bertrand's postulate]])
    * 임의의 정수 n>2 에 대해서 n<p<2n 인 소수 p가 존재한다
    * PS 범위에서는 위의 소수 간극을 이용해서 'n<p<n+1550 인 소수 p가 존재한다' 로 범위를 잡는게 더 유용해서 별로 쓸일이 없을듯.
  * 골드바흐의 추측 ([[wp>Goldbach's conjecture]])
    * 2보다 큰 모든 짝수는 2개의 소수의 합으로 표현할 수 있다.
    * 꼭 이것뿐 아니라, 아직까지 '무슨무슨 추측'으로 남아있는 내용들은 이미 어마어마하게 큰 수까지 다 돌려봤지만 그 안에서는 반례를 못찾았다는 의미이다. 그러니까 PS범위에서는 그냥 다 참이라고 생각하면 된다.
  * 디리클레 등차수열 정리 ([[wp>Dirichlet's theorem on arithmetic progressions]]
    * 첫 수와 항들의 차가 서로소인 등차수열에 무한히 많은 소수들이 포함되어 있다
    * 여기저기에서 가끔 언급되기는 하는데 (이 정리 이름이 제목인 문제도 있고..), 근데 진짜로 이것을 이용해서 접근 또는 증명해야하는 문제는 아직 본적이 없다.

===== 따로 항목이 있는 주제들 =====
  * [[ps:소수 목록 구하기]]
  * [[ps:소수 판별]]
  * [[ps:소인수분해]]
  * [[ps:소수의 개수 구하기]]