Encontrar un número primo después de un número dado

Question

¿Cómo puedo encontrar el número primo mínimo mayor que un número determinado? Por ejemplo, dado 4, necesito 5; dado 7, necesito 11.

Me gustaría conocer algunas ideas sobre los mejores algoritmos para hacer esto. Un método en el que pensé fue generar números primos a través del Tamiz de Eratóstenes, y luego encontrar el primo después del número dado.

Answer 1

algún otro Se han sugerido métodos y creo que son buenos, pero realmente depende de cuánto desee almacenar o calcular en el momento. Por ejemplo, si está buscando el próximo primo después de un número muy grande, entonces usar el Tamiz de Eratóstenes podría no ser tan bueno debido a la cantidad de bits que tendría que almacenar.

Como alternativa, puede verificar todos los enteros impares entre (e incluyendo) 3 y sqrt (N) en cada número número impar N mayor que el número ingresado hasta que encuentre el número correcto. Por supuesto, puede dejar de verificar cuando encuentre que es compuesto.

Si quiere un método diferente, sugiero usar el Miller-Rabin primality test en todos los números impares sobre el número de entrada (suponiendo que la entrada es> 1) hasta que se encuentre un primo. Si sigue la lista, ubicada en la parte inferior de la página, de los números a para verificar los rangos dados, puede reducir significativamente el número de a que debe verificar. Por supuesto, es posible que desee comprobar al menos algunos de los números primos más pequeños (3,5,7,11, por ejemplo) antes de consultar con Miller-Rabin.

Answer 2

Tendría una gran tabla de búsqueda y luego buscar el número dado y responder con el siguiente en la secuencia.

Funciona bien si hay un límite superior conocido (sensible) en el rango de números dados.

Answer 3

Generalmente veo dos formas de hacerlo.

• a contar desde n y control de cada número para que sea primo o no
• generar números primos y comprobar su contra. (quizás haga eso de antemano, utilice una tabla de números primos existente, para que no tenga que calcular cosas cada vez (siempre que N esté dentro del rango de su tabla precalculada)

quizás esto ayude también, (basta con sustituir 2 con su número dado y N con infinita: D) finding all prime numbers between 2 and N

Answer 4

Fuente: Wikipedia

Bertrand's postulate (ac en realidad un teorema) establece que si n> 3 es un número entero, siempre existe al menos un número primo p con n < p < 2n - 2. Una formulación más débil pero más elegante es: para cada n> 1 siempre hay en al menos una prima p tal que n < p < 2n.

Así que si me dan un número, digamos n, de lo que puedo comprobar en el rango (n, 2 * n) [intervalo abierto excluyendo ny 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

He hecho esto antes.

La única adición es el Teorema de Bertrand de Rajendra's Answer.

Y código de fábrica 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; 
} 

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