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