(상대적으로) 숫자에 대한 약수를 빨리 찾으십시오. <10 000 000

Question

천만 이하의 자연수에 대해서만 이야기하고 있다고 가정하십시오.

LPD (14) == 2, LPD (15) == 3, 그리고 LPD (14) == 3과 같이 10 000 미만의 모든 숫자에 대해 LPD (Lowest Prime Divisor) 목록을 미리 생성하려고합니다. 어떤 소수의 LPD는 그 자체입니다.

나는 모든 소수를 미리 생성했습니다. n 번째 프라임에 액세스하는 것은 간단한 배열 조회입니다. 효율성은 다음과 같습니다. O (1)

주어진 숫자가 소수인지 판별하기위한 미리보기 테이블을 미리 생성했습니다. n 번째 프라임에 액세스하는 것은 간단한 배열 조회입니다. 효율성의 : O (1)

이제, 주어진 숫자의 LPD를 계산하는 나의 순진한 알고리즘은 하나의 프라임이 숫자를 나눌 때까지 모든 소수를 반복하는 것입니다. 그러나 이것은 정말로 오랜 시간이 걸립니다. 모든 숫자에 대해 가장 낮은 약수를 찾는 데 걸리는 시간의 절반 만에 천만 이하의 모든 소수를 생성 할 수 있습니다 (Atkin의 체를 사용합니다. 이해할 수는 없지만 의사 코드에서 구현되었습니다).

최저 우선 소수를 계산할 때 더 좋은 알고리즘이 있습니까?

Answer 1

동일한 문제에 대해 왜 더 높은 성능을 기대하는지 실제로는 확신 할 수 없습니다.

나누기보다는 시브 (sieve) 접근법이 각 소수를 취하고, 이미 표시된 경우가 아니라면 모든 배수를 가장 작은 소수 요소로 표시합니다.

int lpf[MAX] = {}; 
int primes[MAX_PRIME]; 

for(int i = 0; i < MAX_PRIME; ++i) 
{ 
    int mult = primes[i]; 
    while(mult < MAX) 
    { 
     if (lpf[mult] == 0) 
     { 
      lpf[mult] = primes[i]; 
     } 
     mult += primes[i]; 
    } 
} 

끝의 도장이 숫자는 자체 소수이기 때문에이 방법은 MAX에서 모든 소수를 찾는 같은 시간이 걸립니다.

키스의 대답 @에서 적응으로

Answer 2

, 새로운 코드는 훨씬 더 빨리 (13 %에게 기존의 속도를!) 실행 :

public void SieveDivisors() { 
     int iNum, iPrime, i6Prime; 
     _iaFirstDivisors = new int[_iLimit]; 
     _iaFirstDivisors[1] = 1; 
     //Start at the largest primes, then work down. This way, we never need to check if the 
     // lowest prime multiple is already found, we just overwrite it 
     //Also, skip any multiples of 2 or 3, because setting those is a waste of time 
     for (int iPrimeIndex = _iaPrimes.Length - 1; iPrimeIndex >= 1; iPrimeIndex--) { 
      iPrime = _iaPrimes[iPrimeIndex]; 
      i6Prime = iPrime * 6; 
      for (iNum = iPrime; iNum < _iLimit; iNum += i6Prime) { 
       _iaFirstDivisors[iNum] = iPrime; 
      } 
      for (iNum = iPrime * 5; iNum < _iLimit; iNum += i6Prime) { 
       _iaFirstDivisors[iNum] = iPrime; 
      } 
     } 
     //Then record all multiples of 2 or 3 
     for (iNum = 3; iNum < _iLimit; iNum += 6) { 
      _iaFirstDivisors[iNum] = 3; 
     } 
     for (iNum = 2; iNum < _iLimit; iNum += 2) { 
      _iaFirstDivisors[iNum] = 2; 
     } 
    } 

Answer 3

당신은 소수의 목록을 생성합니다 Atkin의 체를 사용하고 말한다. Somve of Eratosthenes를 사용하면 자동으로 LPD 배열을 얻을 수 있습니다. 단순히 시브에 사용하는 배열입니다. 부울 트랙을 저장하는 대신 숫자 합성을 만드는 첫 번째 소수를 추적합니다. 배열 lpd[] 가장 낮은 주요 약수를 포함하고 primes[]는 소수의 목록을 포함 할 말

int lpd[MAX] = {}; 
int primes[MAX_PRIMES]; 
int nprimes = 0; 

void sieve() { 
    for (int p = 2; p*p < MAX; ++p) { 
    if (lpd[p] == 0) { 
     primes[nprimes++] = p; 
     lpd[p] = p; 
     for (int q = p*p; q < MAX; q += p) { 
     if (lpd[q] == 0) { lpd[q] = p; } 
     } 
    } 
    } 
} 

: 여기

은 일부 의사 C 코드입니다.