我期待着改进我的算法以找到给定数字右边的下一个素数。 我到目前为止是这样的:
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;
}
}
}
虽然这个算法在经常运行时效率不高。 有人可以就如何加速或改进算法提出建议吗。
最佳答案
当只能找到一个质数时,Eratosthenes 筛法不是最佳解决方案。这是可用于此目的的解决方案。它基于所有素数都是 6k+-1 形式的想法,所以我只测试 2、3 和 6+-1 形式的数字。当然,当除数违反 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;
}
最终结果是这个循环在我试过的几个大数字上运行得非常快。
关于c++ - 寻找下一个素数算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30052316/