查找下一個素數算法

-1

我期待着改進我的算法，找到給定數字右邊的下一個素數。我到目前爲止是這樣的：經常跑時查找下一個素數算法

int NextPrime(int a) 
{ 
    int i, j, count, num; 
    for (i = a + 1; 1; i++) 
    { 
     for (j = 2, count = 0; j <= i; j++) 
     { 
      if (i%j == 0) 
      { 
       count++; 
      } 
     } 
     if (count == 1) 
     { 
      return i; 
      break; 
     } 
    } 
}

芹苴這個算法是不是efficent。有人可以提供有關如何加快或改進算法的建議。

來源

2015-05-05 Dark Side

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes – senfen

的兩個基本速度起坐由2遞增J所示僅奇數（測試2後從3開始，）除2以外的數字是主要數字。此外，只檢查數字的平方根（因爲任何數字的因素之一<=平方根）。 – borrible

另請參見[此相關問題]（http://stackoverflow.com/q/453793/2994596） – SleuthEye

只有一個素數被發現時，Eratosthenes篩不是最好的解決方案。這是對此有用的解決方案。它基於所有素數都是6k + -1形式的想法，所以我只用形式6 + -1測試2,3和數字。當然，循環會因爲除數sqrt（a）而退出，因爲所有這些數字都已經過測試。

bool IsPrime(int number) 
{ 

    if (number == 2 || number == 3) 
     return true; 

    if (number % 2 == 0 || number % 3 == 0) 
     return false; 

    int divisor = 6; 
    while (divisor * divisor - 2 * divisor + 1 <= number) 
    { 

     if (number % (divisor - 1) == 0) 
      return false; 

     if (number % (divisor + 1) == 0) 
      return false; 

     divisor += 6; 

    } 

    return true; 

} 

int NextPrime(int a) 
{ 

    while (!IsPrime(++a)) 
    { } 
    return a; 

}

最終結果是這個循環在我嘗試過的幾個大數字上工作得非常快。

來源

2015-05-05 12:05:00

@MOehm是的，謝謝。固定。 –

函數'IsPrime'並不總是正常工作，例如數字'64144081 = 8009^2'的結果是'true'。 –

嗨@AlexeiShestakov，謝謝你報告這個案子。實際上，我的代碼中的停止條件是錯誤的 - 不是在除數^ 2 <= n時運行，而是必須在（除數-1）^ 2 <= n時繼續循環。很好的邊界條件錯誤的情況下，我會寫下來！你有我的+1。 –

首相是由1號devisible和自身，我們需要檢查1號之間的所有數字

int NextPrime(int a) 
{ 
    int i, j, count, num; 
    for (i = a + 1; 1; i++) 
    { 
     count = 0; 
     for (j = 2;j < i; j++) 
     { 
      if (i%j == 0) // found a devisor 
      { 
       count++; 
       break; // break for (j = 2,j < i; j++) loop 
         // this will speed up a bit 
      } 
     } 
     if (count == 0) 
     { 
      return i; 
      //break; // break for (i = a + 1; 1; i++) loop 
        // break is not needed because return will stop execution of this function 
     } 
    } 
}

來源

2015-05-05 12:10:39 ustmaestro

您可以通過很多在埃拉托色尼的篩改善，如果你只覈對每個每個號碼直到素數的平方根爲止。爲此，你需要保存所有素數列表。這增加了內存的成本，但通過長時間增加執行速度。

僞代碼：

List foundPrimes; 
foundPrimes.add(1) 
foundPrimes.add(2) 

bool isPrime(int x) { 
    for (int divisor in foundPrimes) { 
     if (divisor*divisor > x) { 
      foundPrimes.add(x); 
      return true; 
     } else if (x % divisor==0) { 
      return false; 
     } 
    } 
    // Invalid, need to run the algo from 3 on to fill the list 
} 

int nextPrime(int x) { 
    while (!isPrime(++x)) {} 
    return x; 
}

來源

2015-05-05 14:30:48 Dakkaron

查找下一個素數算法

回答

相關問題