사용자 도구

사이트 도구


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
    • 첫 수와 항들의 차가 서로소인 등차수열에 무한히 많은 소수들이 포함되어 있다
    • 여기저기에서 가끔 언급되기는 하는데 (이 정리 이름이 제목인 문제도 있고..), 근데 진짜로 이것을 이용해서 접근 또는 증명해야하는 문제는 아직 본적이 없다.

따로 항목이 있는 주제들

토론

댓글을 입력하세요:
U L Z U B
 
ps/소수.txt · 마지막으로 수정됨: 2024/01/26 08:22 저자 teferi