cálculo de primos

Question

Según mi conocimiento, he visto las únicas funciones siguientes que producirán primos para $n$ :

1. $n^2 - n + 41$

2. $n^2 + n + 41$

   Por supuesto, ambas funciones fallan para $n = 41$ debido a la representación polinómica. He intentado preparar una función que genere primos continuamente. Como sabemos que los primos son infinitos pero hay un espacio entre ellos y es difícil producir todos los primos en una sola función o algoritmo. Por favor, mira mi algoritmo, que creo que, producirá sólo primos.

#include <iostream>

int testForPrime (int n) {
  int p, i;
  p = 1;
  i = 3;
  int result = n;
  while (i < result) {
      result = n / i;
      if (n == i * result) {
          p = 0;
          i = n;
      }
      i = i + 2;
  }
  return (p);
}
int main (int argc, char * const argv[]) {
  int p, i, n;
  i = 3;
  n = 5;
  std::cout << "Initiating prime number generation sequence...\n\n1:2\n2: 3\n";
  while (1) {
      p = testForPrime (n);
      if (p == 1) {
          std::cout << i << ": " << n << "\n";
          i++;
      }
      n = n + 2;
  }
  return 0;
}

Para una mejor comprensión, por favor, vea el archivo de mi fuente en haciendo clic en EDITAR de mi post.

Me gustaría saber lo siguiente:

1. ¿Es cierto mi algoritmo o puede necesitar más modificaciones?
2. Si restringimos el número de primos menores que x en función de los ceros de la función zeta El primer término es $x/\log(x)$ . La hipótesis de Riemann equivale a la afirmación de que los demás términos están acotados por una constante veces $\log(x)$ veces la raíz cuadrada de $x$ . La hipótesis de Riemann afirma que todos los ceros "no evidentes" de la función zeta son números complejos con parte real $1/2$ . ¿Cómo?

Si se puede dar un poco más de claridad en esta segunda parte, voy a escribir otro algoritmo para la justificación de este segundo problema.

Answer 1

Su código, como señala Peter, es la división de prueba y por eso funciona. (La función testForPrime no maneja casos especiales como 1, potencias de 2 o números negativos, pero su código no le pasará ninguno de ellos). Esto generará correctamente los primos hasta el límite de los enteros en su plataforma.

Hay docenas, probablemente cientos, de algoritmos diferentes que generan primos. Su código es de la variedad "generar y probar" y lleva tiempo $O(n^{3/2+o(1)}).$ Más rápido sería un colador que sólo llevaría tiempo $O(n^{1+o(1)}).$

Las más eficaces a efectos prácticos son las variantes de la criba de Eratóstenes. El más rápido asintóticamente (pero no competitivo en todos los tamaños en los que se ha aplicado) es el tamiz de Atkin-Bernstein.

Answer 2

Sugeriría utilizar las GMP's mpz_nextprime . Aunque se basa en un test de primalidad probabilístico, creo que se ha comprobado completamente que funciona sin problemas dentro de los límites de los enteros de 32 bits. Además, espero que funcione más rápido que tu código.