algorithm - 与えられた数の後に素数を見つける

Question

与えられた数よりも大きい最小の素数を見つけるにはどうすればよいですか？たとえば、4の場合、5が必要です。7が与えられると、11が必要です。

これを行うための最良のアルゴリズムに関するいくつかのアイデアを知りたいです。私が考えた方法の1つは、エラトステネスのふるいを通して素数を生成し、与えられた数の後に素数を見つけることでした。

Answer 1

出典：ウィキペディア

バートランドの公準(実際には定理) は、n > 3 が整数の場合、n < p < 2n − 2 である素数 p が少なくとも 1 つ存在することを示しています。は常に、n < p < 2n を満たす少なくとも 1 つの素数 p です。

したがって、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 2

他のいくつかの方法が提案されており、それらは良いと思いますが、実際にはその場でどれだけ保存または計算する必要があるかによって異なります. たとえば、非常に大きな数の後に次の素数を探している場合、エラトステネスのふるいを使用しても、格納する必要があるビット数が多くなるため、それほど効果的ではない可能性があります。

または、正しい数値が見つかるまで、入力数値よりも大きい奇数 N ごとに 3 と sqrt(N) の間 (および含む) のすべての奇数整数をチェックすることもできます。もちろん、複合であることがわかったら、チェックを停止できます。

別の方法が必要な場合は、素数が見つかるまで、入力数を超えるすべての奇数 (入力が > 1 であると仮定) に対してMiller-Rabin 素数性テストを使用することをお勧めします。ページの下部にあるa、指定された範囲を確認する数値のリストに従うと、確認する必要がある の数を大幅に減らすことができますa。もちろん、Miller-Rabin で確認する前に、少なくともいくつかの小さな素数 (たとえば、3、5、7、11) を確認することをお勧めします。

Answer 3

私は前にこれをやったことがあります。

唯一の追加は、Rajendra's Answerからの Bertrand の定理です。

そして、トップコーダーからの既製のコード。

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

Answer 4

私は一般的にそれを行うための2つの方法を見ています。

• nからカウントアップし、すべての数値が素数であるかどうかを確認します
• 素数を生成し、それらに対してチェックします。（おそらく事前にそれを行い、既存の素数テーブルを使用するので、毎回計算する必要はありません（Nが事前に計算されたテーブルの範囲内にある限り）

たぶんこれも役立つでしょう（2をあなたの与えられた数に置き換え、Nを無限の：Dに置き換えるだけです） 2とNの間のすべての素数を見つけます

Answer 5

私は大きなルックアップテーブルを持っていて、それから与えられた番号を検索し、シーケンスの次の番号で応答します。

与えられた数の範囲に既知の（賢明な）上限がある場合にうまく機能します。

Answer 6

java.util.Scanner をインポートします。

公開クラス Practice11 {

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

}

}