Prime number Theorem으로 알아보는 구간 내의 소수 개수

1. prime number theorem(소수 정리) 양의 실수 x 이하에 존재하는 소수의 개수를 $\pi(x)$라고 한다면 다음이 성립한다. 양수 x이하의 소수의 개수는 근사적으로 x/logx개라는 소리다. 로그 적분 함수 li(x)는 다음과 같이 정의한다. 그래프가 다음과 같다. 구간 [0,x]가 아닌 [2,x]에서 로그 적분 함수를 Li(x)로 나타내기도 한다 이를 이용해서 다음과 같이 나타내기도 한다. 즉, $\pi(x)$는 Li(x)에 근사할 수 있고, 현대에는 이게 더 정확하다고 알려져있다. 2. 소수의 밀도 직관적으로 큰 숫자에서 소수 사이 간격이 점점 커진다는 것을 알 수 있다. 에라토스테네스의 체로 구해보면 알수 있다 그렇게 차이나지는 않네 흠.. 양수..

• format_list_bulleted 정수론
• · 2025. 7. 2.
• textsms

에라토스테네스의 체 변형 segmented sieve 배우기

https://deepdata.tistory.com/393 소수를 빠르게 구하는 에라토스테네스의 체 알고리즘1. 소수를 구하는 방법 컴퓨터가 주어진 수 n이 소수인지 판단할려면 어떻게 해야할까? 1부터 n까지 n에 나눠보면서 n의 약수인지 아닌지 판단해보면 된다. n의 약수가 1과 n만 있어야 n이 소수이다deepdata.tistory.com 에라토스테네스의 체의 문제는 수행하는 연산의 수가 아니라 메모리 요구량에 있다. n이 매우 큰 경우, 소수의 범위가 메모리에 모두 담기지 않을 수 있다. 더 나쁜 것은, n이 그리 크지 않은 경우에도 캐시 사용이 매우 비효율적이라는 점이다. 이 알고리즘은 배열 A 전체를 순차적으로 탐색하며, 참조 지역성이 거의 없다. 이러한 문제에 대한 해결책으로 분할 체(se..

• format_list_bulleted 정수론
• · 2025. 6. 30.
• textsms