查找下一个素数算法

-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

查找下一个素数算法

回答

相关问题