Nth 프라임의 대략적인 값을 찾는 방법이 있습니까?

StackOverflow https://stackoverflow.com/questions/1042717

  •  22-07-2019
  •  | 
  •  

문제

대략적인 값을 반환 할 함수가 있습니까? N 프라임? 나는 이것이 대략적인 역 프라임 카운팅 함수와 같은 것이라고 생각합니다. 예를 들어,이 기능을 25로 부여하면 약 100 숫자를 반환 하거나이 기능을 1000으로 주면 8000 정도의 숫자를 반환합니다. 반환 된 숫자가 프라임인지 아닌지는 상관하지 않지만 원합니다. 그것은 빠르기 위해 N 반환 할 소수 N th.)

먼저 생성 할 수 있도록이를 원합니다. N 체를 사용한 소수 (에라토스테네스 또는 아킨). 따라서 근사치 N 이상적으로는 실제의 가치를 과소 평가하지 않을 것입니다. N 프라임.

(업데이트 : 참조 내 대답 상한을 찾는 좋은 방법을 위해 N TH 소수.)

도움이 되었습니까?

해결책

더 단단한 경계 :

static const unsigned short primes_small[] = {0,2,3,5,7,11};

static unsigned long nth_prime_upper(unsigned long n) {
  double fn = (double) n;
  double flogn, flog2n, upper;
  if (n < 6)  return primes_small[n];
  flogn  = log(n);
  flog2n = log(flogn);

  if      (n >= 688383)    /* Dusart 2010 page 2 */
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn));
  else if (n >= 178974)    /* Dusart 2010 page 7 */
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn));
  else if (n >=  39017)    /* Dusart 1999 page 14 */
    upper = fn * (flogn + flog2n - 0.9484);
  else                    /* Modified from Robin 1983 for 6-39016 _only_ */
    upper = fn * ( flogn  +  0.6000 * flog2n );

  if (upper >= (double) ULONG_MAX) {
     /* Adjust this as needed for your type and exception method */
    if (n <= 425656284035217743UL) return 18446744073709551557UL;
    fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1);
  }

  return (unsigned long) ceil(upper);
}

이것들은 실제 NTH_PRIME보다 작아서는 안되며, 64 비트 입력에 대해 작동해야하며, 이전에 주어진 Robin의 공식 (또는 Wimblik의 복잡한 범위 제한 공식)보다 크기가 높아야합니다. 내가 사용하기 위해 약간 더 큰 작은 프라임 테이블이 있으므로 마지막 견적을 조금 더 강화할 수 있습니다. 기술적으로 공식에서 우리는 Ceil () 대신 Floor ()를 사용할 수 있지만 정밀도에 대해 걱정합니다.

편집 :이 비트를 개선하기위한 또 다른 옵션은 우수한 프라임 카운트 경계 (예 : Axler 2014)를 구현하고 이진 검색을 수행하는 것입니다. 이 방법에 대한 내 코드는 위의 것보다 ~ 10x 더 길어 (여전히 밀리 초 미만으로 실행됨) 오류 백분율을 크기로 줄일 수 있습니다.

Nth Prime에 대한 견적을 원한다면 다음을 수행 할 수 있습니다.

  • Cipolla 1902 (참조 Dusart 1999 12 페이지 또는 이 종이. 3 가지 용어 (M = 2)와 3 차 보정 계수가 유용하지만 더 많은 용어로 너무 진동합니다. Wikipedia 링크에 표시된 공식은이 공식입니다 (m = 2). 아래의 2 기 역 Li 또는 역 Riemann R을 사용하면 더 나은 결과를 얻을 수 있습니다.
  • DUSART 2010 상한 및 하한을 계산하고 결과를 평균화하십시오. 너무 나쁘지는 않지만 가중 평균을 사용하면 경계가 똑같이 빡빡하지 않기 때문에 더 잘 작동한다고 생각합니다.
  • li^{-1} (n) Li (n)은 프라임 카운트에 대한 괜찮은 근사치이므로 역은 괜찮은 nth_prime 근사입니다. 이것은 기능에 대한 이진 검색으로 상당히 빠르게 수행 할 수 있습니다.
  • li^{-1} (n) + li^{-1} (sqrt (n))/4 더 가까워 져서 r (n)에 가까워지기 때문입니다.
  • R^{-1} 역 Riemann R 함수는 내가 아는 가장 가까운 평균 근사치입니다.

마지막으로 LMO 구현 중 하나 (현재 세 가지 오픈 소스 구현이 있음)와 같은 매우 빠른 프라임 카운트 방법이있는 경우 빠른 정확한 NTH_PRIME 메소드를 작성할 수 있습니다. 10^10 번째 프라임을 계산하는 것은 몇 밀리 초 안에, 그리고 몇 초 안에 10^13 위 (현대 고속 기계에서)를 수행 할 수 있습니다. 근사치는 모든 크기에서 매우 빠르며 훨씬 더 많은 숫자로 작동하지만 모든 사람은 "큰"의 의미에 대한 다른 아이디어를 가지고 있습니다.

다른 팁

그 모든 답변에 감사드립니다. 나는 그렇게 간단한 것이 있다고 의심했지만 당시에는 그것을 찾을 수 없었습니다. 나도 조금 더 연구를 해냈습니다.

나는 그것을 원한다 체 첫 번째를 생성합니다 N 소수, 나는 근사치가 N프라임. (그러므로 나는 상한을 원한다 NTH 소수.)

위키 백과 다음과 같은 상한을 제공합니다 n >= 6

p_n <= n log n + n log log n   (1)

어디 p_n 입니다 NTh Prime, 그리고 log 자연 로그입니다. 이것은 좋은 시작이지만, 불가능한 금액으로 과대 평가할 수 있습니다. 이 기사 안에 대학 수학 저널 더 단단한 상한을 제공합니다 n >= 7022

p_n <= n log n + n (log log n - 0.9385)   (2)

다음 표에서 보여지는 것처럼 이것은 훨씬 더 단단합니다.

n         p_n         approx 1    error%  approx 2    error%
1         2                            
10        29          31          6.90 
100       541         613         13.31
1000      7919        8840        11.63
10000     104729      114306      9.14    104921      0.18
100000    1299709     1395639     7.38    1301789     0.16
1000000   15485863    16441302    6.17    15502802    0.11
10000000  179424673   188980382   5.33    179595382   0.10

나는 내 구현했다 N두 번째 근사치를 사용하는 주요 근사 기능 n >= 7022, 첫 번째 근사치 6 <= n < 7022, 및 처음 5 소수에 대한 배열 조회.

(첫 번째 방법은 특히 내가 사용하는 범위에 대해 매우 단단하지는 않지만 체를 위해 이것을 원하기 때문에 걱정하지 않으며 더 작은 숫자의 체는 계산적으로 저렴합니다.)

소수 정리 임계 값 미만의 여러 프라임을 제공하므로 Nth 프라임에 대한 대략적인 값을 제공하는 데 사용될 수 있습니다.

대략적인 추정치로, n*ln (n)을 nth 소수의 근사치로 사용할 수 있습니다. Wikipedia에서 찾을 수있는 훨씬 더 복잡하지만 더 정확한 방법이 있습니다. 여기.

나의 최고의 프라임 (n) 추정치

1/2*(8-8.7*n-n^2+
1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+
abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+
abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2))))))

가장 최근의 더 실험적인 공식은 다음과 같습니다. BTW. 10 조 프라임입니다 323,780,508,946,331 이 공식은 그 척도에서 매우 잘 작동합니다. n*ln(n)+n*(ln(ln(n))-0.9385). 

1/2*(3-(8+ln(2.3))*n-n^2+1/2*(-1+
abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+
(8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/
ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/
ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/
ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/
ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))*
ln(ln((n*ln(8*n))/ln(n))/ln(2)))))))

체로 효율적인 구현은 불가능할 것입니다. 처음 10.000 소수를 원한다면 어떻게 될지 생각해보십시오. 아마도 당신은 아마도 큰 양의 숫자에 대한 체를 만들어야 할 것입니다.

당신의 자신의 이탈 이 질문 그리고 내 대답 승인을 모르고 이것을 구현하는 좋은 방법입니다. 프라임의 가치

Dana J의 상한을 보완하기 위해이 공식은 당신에게 좋은 하한을 제공해야합니다.

P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n;
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top