找到下一个素数算法

Question

我期待着改进我的算法,找到给定数字右边的下一个黄金编号.到目前为止我所拥有的是:

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;
        }
    }
}

经常运行时,这种算法并不那么有效.有人可以提出有关如何加快或改进算法的建议.

Answer 1

当只能找到一个素数时,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;

}

最终的结果是,这个循环在我试过的几个大数字上运行得非常快.