두 개의 숫자 사이에 소수의 수를 찾을 수있는 빠른 알고리즘

Question

내 문제는 주어진 두 numbers 사이의 소수의 수를 발견하는 것으로 감소합니다. 1 to (1000)!만큼 큰 범위를 가질 수 있으므로 수학적 최적화가 필요합니다.

분명히 체 방법은이 경우 너무 느릴 것입니다. 적용 할 수있는 수학적 최적화가 있습니까? 예를 들어,이 큰 공간의 더 작은 하위 세트를 가져 와서 나머지 숫자에 대한 추론을하는 것과 같습니다.

P .: 분명히 막 다른 골목에 다다 랐을 것 같습니다. 그러나 내가 찾고있는 모든 것들은 이것을 해결하는 데 도움이 될 수있는 최적화입니다. 또한 단일 스레드 접근 방식만을 찾고 있습니다.

EDIT : 하나의 접근법으로 많은 소수의 큰 소수점 문제를 해결할 수 있습니다. 누군가가 글로벌 소수 테이블을 유지 관리하고이를 조회 할 수있게하는 것입니다. PrimeGrid 프로젝트에 참여한 사람들은 이에 대해 유용하게 기여할 수 있습니다.

Answer 1

1000! (계승)만큼 올라 가기를 원합니다. 현재 기술에서 현재 알려진 방법으로는 정확한 결과를 얻을 수 없습니다.

Prime Counting Function은 10^24까지 소수의 값으로 정확하게 평가되었습니다. 따라서 1000! 명중 할 수는 없습니다.

---

그러나 당신이 잘 될 수있는 근사보다 언급하기 때문에, 당신은 국무 계수 기능에 근사치로 Logarithmic Integral를 사용할 수 있습니다.

Prime Number Theorem에 기초한 것으로, 프라임 계수 기능은 로그 적분에 점근 적이라고합니다.

Answer 2

내가 알고있는 가장 빠른 방법은 알려진 비 - 소수 (짝수, 모든 숫자가 범위의 시작 숫자보다 낮은 등)를 가능한 빨리 제거한 다음 다시 반복하는 것입니다. 나머지는 Euclidean algorithm과 같은 것을 사용하여 해당 숫자가 소수인지 확인하십시오.

Answer 3

현재 옵션을 조사 할 수 있습니다 http://en.wikipedia.org/wiki/Prime_counting_function

를 이것은 또한 도움이 보인다 : 당신이 1000 그것을 필요한 이유 http://mathworld.wolfram.com/PrimeCountingFunction.html

내가 문의 바랍니다! ? 아무도 그 전에 많은 것을 셀 수 없었던 것처럼 보입니다. 1-10^23의 1,925,320391606803,968,923 개의 소수가 있습니다. 1000! = 10^120. 나는 지금 호기심이 많다.

Answer 4

주어진 경계 아래에 소수의 수에 대한 fast, simple approximation가 있습니다. 정확한 값이 필요하지 않은 경우이 수식의 두 가지 평가의 차이로 인해 닫힐 수 있습니다.

Answer 5

다른 사람들이 인용 한 Lagarias 및 다른 사람들이 개발 한 소수 계산 알고리즘은 O (n^(2/3))에서 매우 대략 실행됩니다. k1에서 k2까지의 소수에 대한 체는 대략 O (max (sqrt (k2), k2 - k1)를 취하기 때문에 상한과 하한이 얼마나 떨어져 있는지 확인하고 체로하거나 소수 계산 알고리즘을 사용합니다 어느 쪽이든 빠른 것

BTW. 소수 계산은 개별적으로 계산하는 것보다 합리적으로 가까운 다양한 값 n에 대해 1부터 n까지의 소수를 계산하도록 조정할 수 있습니다.(기본적으로 숫자 N을 선택하고 크기 n/N의 체를 만들고 그 체에서 N^2 값을 찾습니다 .O (n^(2/3))은 N = (1/3) 두 작업 모두 N^(2/3) 단계를 취합니다.이 체는 다른 n에 대해 재사용 할 수 있지만 다른 값을 찾아야합니다. 따라서 k의 다른 값 n에 대해 N을 조금 더 작게 만들고, 체 (한 번만)의 비용을 증가 시키지만 조회 비용 (k 배)을 줄입니다.

n이 약 1000 인 경우, 기회가 없습니다. n에 작은 (ish) 요소가없는 경우 [n, n]에있는 소수의 수를 계산할 수도 없습니다.