在给定数字后查找质数

Question

如何找到大于给定数的最小质数？例如，给定4，我需要5；给定7，我需要11。

我想知道一些关于做这件事的最佳算法的想法。我想到的一种方法是通过Eratosthenes的筛子产生质数，然后在给定的数字之后找到质数。

Answer 1

还有一些其他的方法，我认为它们是好的，但这真的取决于你想要在现场存储或计算多少。例如，如果您正在寻找一个非常大的数字之后的下一个质数，那么使用Eratosthenes筛子可能不会那么大，因为您需要存储的位数。

或者，您可以在每个大于输入数字的奇数N上检查3和sqrt(N)之间的所有奇数整数，直到找到正确的数字。当然，当你发现它是复合的时，你可以停止检查。

如果你想要一种不同的方法，那么我建议对输入数字(假设输入大于1)上的所有奇数使用Miller-Rabin primality test，直到找到质数。如果您按照页面底部的numbers a列表检查给定的范围，则可以显著减少需要检查的a数量。当然，在检查Miller-Rabin之前，您可能希望至少检查几个较小的素数(例如3，5，7，11)。

Answer 2

来源：维基百科

Bertrand's postulate (实际上是一个定理)指出，如果n>3是整数，则总存在至少一个素数p，其中n1，总有至少一个素数p使得n

因此，如果给我一个数字，比如说n，那么我可以检查范围(n，2*n)开放区间，不包括n和2*n

int GetNextPrime(int n)
{
    bool isPrime = false;
    for (int i = n; i < 2 * n; ++i)
    {
    // go with your regular prime checking routine
    // as soon as you find a prime, break this for loop
    }
}

Answer 3

我以前也这么做过。

唯一的加法是来自Rajendra's Answer的伯川德定理。

和来自topcoder的现成代码。

#include<iostream>
using namespace std;

/* This function calculates (ab)%c */
int modulo(int a,int b,int c){
    long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return x%c;
}

/* this function calculates (a*b)%c taking into account that a*b might overflow */
long long mulmod(long long a,long long b,long long c){
    long long x = 0,y=a%c;
    while(b > 0){
        if(b%2 == 1){
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}

/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
bool Miller(long long p,int iteration){
    if(p<2){
        return false;
    }
    if(p!=2 && p%2==0){
        return false;
    }
    long long s=p-1;
    while(s%2==0){
        s/=2;
    }
    for(int i=0;i<iteration;i++){
        long long a=rand()%(p-1)+1,temp=s;
        long long mod=modulo(a,temp,p);
        while(temp!=p-1 && mod!=1 && mod!=p-1){
            mod=mulmod(mod,mod,p);
            temp *= 2;
        }
        if(mod!=p-1 && temp%2==0){
            return false;
        }
    }
    return true;
}

int main(int argc, char* argv[])
{

    int input = 1000;
    int i = 0;

    if(input%2==0)
        i = input+1;
    else i = input;

    for(;i<2*input;i+=2) // from Rajendra's answer
        if(Miller(i,20)) // 18-20 iterations are enough for most of the applications.
            break;
    cout<<i<<endl;

    return 0;
}