41

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

我想知道一些关于最佳算法的想法。我想到的一种方法是通过埃拉托色尼筛生成素数，然后在给定数之后找到素数。

4

8 回答 8

27

来源：维基百科

Bertrand 的公设（实际上是一个定理）指出，如果 n > 3 是一个整数，那么总是存在至少一个质数 p 且 n < p < 2n - 2。一个更弱但更优雅的公式是：对于每个 n > 1 存在总是至少有一个素数 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
    }
}
于 2010-03-18T20:36:56.197 回答
9

已经提出了一些其他方法，我认为它们很好，但这实际上取决于您希望在现场存储或计算多少。例如，如果您正在寻找一个非常大的数字之后的下一个素数，那么使用埃拉托色尼筛法可能不是那么好，因为您需要存储的位数。

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

如果您想要不同的方法，那么我建议对输入数以上的所有奇数（假设输入> 1）使用Miller-Rabin 素数测试，直到找到素数。如果您按照位于页面底部的数字列表a来检查给定范围，则可以显着减少a需要检查的 s 数量。当然，在使用 Miller-Rabin 进行检查之前，您可能需要检查至少几个较小的素数（例如 3、5、7、11）。

于 2010-03-19T05:58:08.367 回答
7

我以前做过。

唯一的补充是来自Rajendra's Answer的 Bertrand 定理。

以及来自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;
}
于 2010-03-20T21:25:09.700 回答
2

我通常看到两种方法来做到这一点。

  • 从 n 开始计数并检查每个数字是否为素数
  • 生成素数并检查它们。（也许事先这样做，使用现有的素数表，所以你不需要每次都计算东西（只要 N 在你预先计算的表的范围内）

也许这也有帮助，（只需将 2 替换为给定的 Number 并将 N 替换为无限 :D ） 查找 2 和 N 之间的所有素数

于 2010-03-18T08:54:32.903 回答
1

我有一个大的查找表，然后搜索给定的数字，并用序列中的下一个进行响应。

如果给定数字的范围有一个已知的（合理的）上限，则效果很好。

于 2010-03-18T08:53:07.133 回答
0 
        int length = number;
        bool flag = true;
        for (int i = number; i <= length; i++)
        {
            for (int k = 2; k < length; k++)
            {
                if (i != k && i % k == 0)
                {
                    flag = false;
                    length = length + 1;
                    break;
                }
            }

            if (flag)
            {
                Console.WriteLine(i);
            }
            flag = true;
        }
于 2021-02-26T03:29:29.720 回答
0

导入 java.util.Scanner；

公共课练习11 {

public static void main(String[] args) 
{
    int count=0;
    Scanner scan=new Scanner(System.in);
    System.out.println("enter a number:");
    int a=scan.nextInt();
    
   a: for(int i=a+1;i<a+1000;i++)// a+1000 because it will check up to 
                                //that number to find the next prime 
    {
        count=0;
        for(int j=2;j<i;j++)
        {
            if(i%j==0) //this will check if a number is divisible by another 
                       // number
            {
            count++;
            }
            else
            {
            }
           }
        if(count==0)
        {
            System.out.println(i);
            break a;//this line will break the loop so you get only one prime 
                      //number 
        }
    }

}

}

于 2022-01-18T15:05:56.153 回答
-1 
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;
    }
于 2017-05-18T19:07:21.117 回答