Trouver un nombre premier après un nombre donné

D'autres méthodes ont été proposées et je pense qu'ils sont bons, mais cela dépend vraiment de combien vous voulez avoir à stocker ou de calcul sur place. Par exemple, si vous êtes à la recherche pour le prochain premier après un très grand nombre, puis à l'aide du Crible d'Eratosthène peut-être pas si grande en raison du nombre de bits que vous aurait besoin de stocker.

Alternativement, vous pouvez vérifier tous les entiers impairs entre (et y compris) 3 et sqrt(N) sur chaque nombre impair de N plus grand que le nombre d'entrée jusqu'à ce que vous trouver le bon numéro. Bien sûr, vous pouvez arrêter la recherche lorsque vous trouvez qu'il est composite.

Si vous souhaitez une autre méthode, alors je vous recommande d'utiliser le De Miller-Rabin test de primalité sur tous les nombres impairs ci-dessus le nombre d'entrée (en supposant que l'entrée est > 1) jusqu'à ce qu'un premier est trouvé. Si vous suivez la liste située au bas de la page, de numéros de a pour vérifier les plages, vous pouvez réduire de manière importante le nombre de as vous avez besoin de vérifier. Bien sûr, vous pourriez vouloir vérifier au moins quelques-uns des plus petits nombres premiers (3,5,7,11 par exemple) avant de vérifier avec Miller-Rabin.

Je l'ai fait avant.

Seul ajout est de Bertrand Théorème de Rajendra Réponse.

Et readymade code de 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;
}

J'aurais une grande table de recherche et ensuite de rechercher le nombre donné et d'y répondre avec la personne suivante dans la séquence.

Fonctionne bien que s'il est connu (sensible) limite supérieure de la gamme de nombres donnés.