Ricerca di un numero primo dopo un dato numero

Question

Come posso trovare il numero primo più grande di un numero dato? Ad esempio, dato 4, ho bisogno di 5; dato 7, ho bisogno di 11.

Mi piacerebbe conoscere alcune idee sui migliori algoritmi per fare questo. Un metodo che pensavo era generare numeri primi attraverso il Sieve di Eratostene, e poi trovare il primo dopo il numero dato.

Answer 1

Qualche altro i metodi sono stati suggeriti e penso che siano buoni, ma in realtà dipende da quanto si vuole archiviare o calcolare sul posto. Per esempio se stai cercando il prossimo primo dopo un numero molto grande, allora usare il Sieve di Eratostene potrebbe non essere così grande a causa del numero di bit che avresti bisogno di memorizzare.

In alternativa, è possibile controllare tutti gli interi dispari tra (e compresi) 3 e sqrt (N) su ogni numero dispari N maggiore del numero di input finché non si trova il numero corretto. Ovviamente puoi smettere di controllare quando trovi che è composito.

Se si desidera un metodo diverso, suggerirei di utilizzare Miller-Rabin primality test su tutti i numeri dispari sopra il numero di input (supponendo che l'input sia> 1) finché non viene trovato un primo. Se si segue l'elenco, situato nella parte inferiore della pagina, dei numeri a per verificare gli intervalli specificati, è possibile ridurre in modo significativo il numero di a s che è necessario controllare. Certo, potresti voler controllare almeno alcuni dei numeri primi più piccoli (3,5,7,11 per esempio) prima di controllare con Miller-Rabin.

Answer 2

Avrei una tabella di ricerca grande e quindi cercarlo per il numero dato e rispondere con il prossimo nella sequenza.

Funziona bene se esiste un limite superiore noto (sensibile) nell'intervallo di numeri indicati.

Answer 3

Generalmente vedo due modi per farlo.

• il conteggio da n e controllando ogni numero al fatto che è primo o no
• generare numeri primi e verificare contro di loro. (magari farlo prima, usa una tabella di primenumber esistente, quindi non devi calcolare ogni volta (anche se N è all'interno della tabella precalcolata)

forse questo aiuta anche, (semplicemente sostituire il 2 con il dato numero e N con infinita: D) finding all prime numbers between 2 and N

Answer 4

Fonte: Wikipedia

Bertrand's postulate (ac un teorema) afferma che se n> 3 è un numero intero, allora esiste sempre almeno un numero primo p con n < p < 2n - 2. Una formulazione più debole ma più elegante è: per ogni n> 1 c'è sempre a almeno un primo p tale che n < p < 2n.

Quindi, se mi viene data un numero, diciamo n, che posso controllare nel campo (n, 2 * n) [aperto intervallo escluso n e 2 * n]

int GetNextPrime(int n) 
{ 
    bool isPrime = false; 
    int i = n; 
    for (; i < 2 * n; ++i) 
    { 
    // go with your regular prime checking routine 
    // as soon as you find a prime, break this for loop 
    } 
} 

Answer 5

L'ho già fatto.

Unica aggiunta è il Teorema di Bertrand da Rajendra's Answer.

E codice readymade da 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 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; 
    }