메이셀-레머 알고리즘

Meissel–

마이스셀-레머 알고리즘(Ernst Meisel, Derrick Henry Lehmer 이후)은 프라임 카운팅 함수의 정확한 값을 계산하는 알고리즘이다.[1][2]

설명

x보다 작거나 같은 정확한 소수 수를 세는 문제는 실제로 모두 나열하지 않고 레전드르에서 비롯된다.에라토스테네스의 체에서 다음과 같이 관찰하였다.

여기서 바닥 기능이며, x보다 작거나 같은 최대 정수를 나타내며 p 는 모든 prime / 2}}회 실행된다[1][2]

이 합계 공식의 평가가 점점 더 복잡해지고 large x에 대해 혼란스러워지기 때문에, 메이셀은 에라토스테네스의 체에 있는 숫자의 계산을 단순화하려고 노력했다.따라서 그와 레머는 아래에 자세히 설명되어 있는 특정한 체 기능을 소개했다.

주요 기능

, 2, 를 첫 번째 n 프리타임으로 한다.자연수 a ≥ 1에 대해 정의

모든 주요 요인이 x 이하의 자연수를 계산하고 자연수 k에 대해서도 정의한다

이것은 정확히 k개의 주요 인자를 가진 x보다 크지 않은 자연 숫자를 세고, 모두 보다 크다 이것들로 우리는

where the sum only has finitely many nonzero terms, because when . Using the fact that , we get

() (를) 계산하여 k ≥ 2에 대해 ) (, 을(를) 계산한다는 것을 증명한다.미셀은 이렇게 말했다.레머 알고리즘은 그렇다.

Pk(x, a)에 대한 공식

k = 2의 경우 k( ,) 에 대해 다음 공식을 구한다

k의 경우 P (x ,)에 대한 ID도 유사하게 파생될 수 있다.[1]

𝜑(x, a) 확장

반복 사용

( ,) 을(를) 확장할 수 있다.각 합계는 차례로 같은 방식으로 확장될 수 있다.

용어 조합

and ( , a (,의 특정 에 대해 x와 a의 평가만 하면 된다.이것은 직접 체에 거르고 위의 공식을 사용하여 할 수 있다.

역사

Meissel already found that for k ≥ 3, if . He used the resulting equation for calculations of for big values of . [1]

메이스셀은 최대 x 값에 대해 ( ))}을를) 계산했지만 x의 가장 큰 값에 대한 정확한 결과를 아슬아슬하게 놓쳤다.[1]

Lehmer는 이 방법과 IBM 701을 사용하여 ( 9의 정확한 값을 계산해 낼 수 있었고, ) 의 정확한 값을 1만큼 누락시켰다.[1]

확장 알고리즘

제프리 Lagarias, 빅터 밀러와 앤드류는 Odlyzko는 π 시간에()){\displaystyle \pi())}O어떤ε하고 우주{O(x^{2/3+\varepsilon})\displaystyle}O(x1/3+ε){O(x^{1/3+\varepsilon})\displaystyle}(x2/3+ε);0{\displaystyle \va를 계산하는 알고리즘의 현실화를 출간했다.사원[2]. = / 3 a를 설정할 ( ,) 트리는 ( / ) O 노드가 있다.[2]

이 확장된 Meissel-Lehmer 알고리즘은 특히 x의 큰 값에 대해 Meissel과 Lehmer가 개발한 알고리즘보다 더 적은 컴퓨팅 시간을 필요로 한다.

알고리즘의 추가 개선은 M에 의해 주어진다.1996년 위임과 J. 리바트.[3]

참조

  1. ^ a b c d e f Lehmer, Derrick Henry (April 1, 1958). "ON THE EXACT NUMBER OF PRIMES LESS THAN A GIVEN LIMIT". Illinois J. Math. 3 (3): 381–388. Retrieved February 1, 2017.
  2. ^ a b c d Lagarias, Jeffrey; Miller, Victor; Odlyzko, Andrew (April 11, 1985). "Computing : The Meissel–Lehmer method" (PDF). Mathematics of Computation. 44 (170): 537–560. doi:10.1090/S0025-5718-1985-0777285-5. Retrieved September 13, 2016.
  3. ^ Deleglise, Marc; Rivat, Joël (January 15, 1996). "Computing : The Meissel, Lehmer, Lagarias, Miller, Odlyzko method". Mathematics of Computation. 65 (213): 235–245. doi:10.1090/S0025-5718-96-00674-6.