Trouver un nombre premier après un nombre donné

Question

Comment puis-je trouver le plus petit nombre premier supérieur à un nombre donné? Par exemple, avec 4, j'ai besoin 5; 7 donné, je dois 11.

Je voudrais savoir quelques idées sur les algorithmes pour le faire. Une méthode que je pensais était générer des nombres premiers par le crible d'Eratosthène, puis trouver le premier après le nombre donné.

Answer 1

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 calculer sur place. Par exemple, si vous êtes à la recherche de la prochaine prime après un très grand nombre, puis en utilisant le Crible d'Eratosthène peut-être pas si grand en raison du nombre de bits dont vous auriez besoin de stocker.

Vous pouvez vérifier tous les entiers impairs entre (et y compris) 3 et sqrt (N) sur chaque nombre nombre impair N supérieur au nombre d'entrée jusqu'à ce que vous trouviez le numéro correct. Bien sûr, vous pouvez arrêter de vérifier quand vous trouvez qu'il est composite.

Si vous voulez une autre méthode, je suggère d'utiliser le Miller-Rabin essai primality sur tous les nombres impairs au-dessus du numéro de l'entrée (en supposant que l'entrée est> 1) jusqu'à ce qu'un premier se trouve. Si vous suivez la liste, située au bas de la page, des numéros a pour vérifier les plages données, vous pouvez réduire de manière significative sur le nombre de as que vous devez vérifier. Bien sûr, vous pouvez vérifier au moins quelques-unes des plus petits nombres premiers (3,5,7,11 par exemple) avant de vérifier avec Miller-Rabin.

Answer 2

Source : Wikipédia

  

postulat de Bertrand (en fait un théorème) indique que si n> 3 est un nombre entier , alors il existe toujours au moins un nombre premier p avec n

1, il y a toujours au moins un premier p tel que n

Donc, si on me donne un certain nombre, disons n, que je ne peux vérifier dans la gamme (n, 2 * n) [intervalle ouvert hors n et 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

Je l'ai fait avant.

Seule l'addition est le théorème de Bertrand de Réponse de Rajendra .

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

Answer 4

Je vois généralement deux façons de le faire.

• comptage de n et de vérifier chaque numéro pour qu'il soit premier ou non
• générer des nombres premiers et vérifier contre eux. (Peut-être faire cela à l'avance, utilisez une table primenumber existante, de sorte que vous n'avez pas besoin de calculer des choses à chaque fois (et aussi longtemps que N est dans la plage de votre table précalculée)

peut-être cela aide aussi, (il suffit de remplacer 2 avec votre numéro donné et N avec infini: D) trouver tous les nombres premiers entre 2 et N

Answer 5

J'ai une grande table de recherche et recherche, puis pour le nombre donné et répondre à la suivante dans la séquence.

fonctionne bien s'il y a un connu (sensible) limite supérieure de la gamme des nombres donnés.

Answer 6

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