소수 (Prime number)

소수의 갯수는 무한히 많다

n이하의 소수의 개수는 대략 n/ln(n)개이다. 바꿔쓰면, n번째 소수의 값은 대략 n*ln(n)이다

실제 백만(10^6) 이하 소수의 개수는 약 8만개. 10억(10^9) 이하 소수의 갯수는 약 5천만개. (링크)

https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities

n이하 소수들의 역수의 합은 O(lnln(n))

이론상 상한은 없지만, 2^64 이하 범위에서는 소수 간극이 1550 이하이다. 2^32 이하 범위에서는 464 이하.

이로부터 n에서 가장 가까운 소수를 찾기 위해서는, 그냥 최대 O(464)개의 수에 대해서 소수여부를 확인하면 된다는 것을 알수 있다.

임의의 정수 n>2 에 대해서 n<p<2n 인 소수 p가 존재한다

PS 범위에서는 위의 소수 간극을 이용해서 'n<p<n+1550 인 소수 p가 존재한다' 로 범위를 잡는게 더 유용해서 별로 쓸일이 없을듯.

2보다 큰 모든 짝수는 2개의 소수의 합으로 표현할 수 있다.

꼭 이것뿐 아니라, 아직까지 '무슨무슨 추측'으로 남아있는 내용들은 이미 어마어마하게 큰 수까지 다 돌려봤지만 그 안에서는 반례를 못찾았다는 의미이다. 그러니까 PS범위에서는 그냥 다 참이라고 생각하면 된다.

첫 수와 항들의 차가 서로소인 등차수열에 무한히 많은 소수들이 포함되어 있다

여기저기에서 가끔 언급되기는 하는데 (이 정리 이름이 제목인 문제도 있고..), 근데 진짜로 이것을 이용해서 접근 또는 증명해야하는 문제는 아직 본적이 없다.