在给定数之后查找素数

有人提出了一些其他的方法,我认为它们很好,但这实际上取决于您需要在现场存储或计算多少。例如,如果你在一个非常大的数之后寻找下一个素数,那么使用埃拉托色尼的筛子可能就不那么好了,因为你需要存储的比特数。

或者,您可以检查(包括)3和sqrt(n)之间的所有奇数,对于每个大于输入数的奇数n,直到找到正确的数字。当然,当您发现它是复合的时,您可以停止检查。

如果你想要一个不同的方法,那么我建议使用 Miller-Rabin primality test 在输入数字上方的所有奇数上(假设输入为>1),直到找到质数。如果您遵循位于页面底部的数字列表 a 要检查给定的范围,可以显著减少 一 你需要检查一下。当然,在与米勒·拉宾核对之前,你可能需要至少核对一些较小的素数(例如3,5,7,11)。

来源 : 维基百科

Bertrand's postulate (实际上是一个定理)指出,如果n>3是一个整数,那么总有至少一个质数p与n<p<2n_ 2。一个更弱但更优雅的公式是:对于每个n>1,总是至少有一个prime p,这样n<p<2n。

因此,如果给我一个数字,比如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
    }
}

我以前做过。

唯一的加法是伯特兰定理 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;
}

我一般认为有两种方法可以做到这一点。

• 从n开始计数并检查每个数字是否为素数
• 生成质数并对照它们进行检查。(也许可以事先这样做,使用现有的素数表,这样就不需要每次都计算东西(只要n在预先计算的表的范围内)

也许这也有帮助(只需将2替换为给定的数字,将n替换为无穷大:d) finding all prime numbers between 2 and N

我会有一个大的查找表,然后搜索给定的数字,然后按顺序用下一个回答。

如果给定数字的范围有一个已知的(合理的)上限,就可以很好地工作。

private static int nextPrime(int num) {
        num++;
        for (int i = 2; i <num; i++) {
            if(num%i == 0) {
                num++;
                i=2;
            } else{
                continue;
            }
        }
        return num;
    }