Generar los "n" primeros numeros primos

[gabyweb]

Hola, estoy que sufro con este aparente sencillo problema.
La idea es ingresar un numero, por ejemplo "8" y debe darme como resultado los 8 primeros numeros primos.

Alguien tiene alguna idea de cómo hacerlo?

Gracias

[AlvaroG]

No es un problema tan sencillo como parece.

Creo que lo mejor es generar una lista de primos y actualizarla (ampliarla) cada vez que alguien pregunta por un número mayor que el máximo que tenés.

Esto tiene doble ventaja:
- No tenés que calcularlo todo cada vez
- ya sabés qué números son primos, por lo que tenés que revisar solamente desde tu máximo hasta el número ingresado.

Bueno, de entrada sabés que 1, 2 y 3 son primos, ¿no?
(el cero queda como discutible)

Sea n el número ingresado:
Paso 1º.- se divide entre 2
Si el resto es 0, se pasa al siguiente paso (ya sé que N no es primo)
Si el resto es 1, se divide entre 3 y se vuelve a comprobar el resto.
Así sucesivamente hasta llegar a dividir entre N/2 (o N/2 +1), considerando que estoy buscando solamente números enteros. (N/ (N/2 + 1) ) > 1 y < 2 para todo n
Si ninguna división tiene resto 0, el número es primo.

Paso 2º: Una vez que se llega a la división cuyo resto es 0, se reinicia el proceso, esta vez con (N-1).
(Por supuesto que puede hacerse al revés, partir de 4 hasta N)

Como ves no es un método eficiente (sobretodo para números grandes), por eso te decía lo de guardar una lista.

Creo que con eso es suficiente como para crear el código acorde.


Saludos.

[AlvaroG]

Bueno, ahora pensé un poco mejor el código correspondiente.

Sea $n el número que tenés.

Código PHP:

  # $actual es el número que estoy revisando (comienza por $n)
 
for ($actual = $n; $actual > 3; $actual--) {
 
for ($div = 2; $div <= ($n/2); $div++) {
 if ( $actual % $div == 0 ) {
  $divide = true;
  break;
  }
 else {
  $divide = false;
  }
 }
 
# si salí por el break, $divide = true;, si terminé el for, $divide = false
if (!$divide) {
 $primos[(count($primos)] = $actual;
 }
} 
   

Teniendo una lista, podrías solamente revisar los primos que ya tenés (en vez de revisar todos los números) para ver si dividen a los que querés averiguar.

Saludos.

[gabyweb]

Estoy tratando de probar tu codigo y no me muestra nada

[AlvaroG]

es que no le puse ninguna salida, quizás quieras hacer algo como:

Código PHP:

  foreach($primos as $numero) {
 echo "$numero es primo<br/>\n";
 } 
   

[gabyweb]

No entiendo mucho tu código si $n=8, por ejemplo debería mostrarme : 1-2-3-5-7-11-13-17, y eso no lo está haciendo

[AlvaroG]

Bueno, revisado y funcionando.

Código PHP:

  <?php 
# $actual es el número que estoy revisando (comienza por $n) 
 
$n = 100;
$primos = array(1, 2, 3);
 
for ($actual = 4; $actual <= $n; $actual++) { 
 
for ($div = 2; $div <= (($actual / 2) + 1); $div++) { 
 if ( $actual % $div == 0 ) { 
  $divide = true; 
  break; 
  } 
 else { 
  $divide = false; 
  } 
 } 
 
# si salí por el break, $divide = true;, si terminé el for, $divide = false 
if (!$divide) { 
 $primos[count($primos)] = $actual; 
 } 
}
 
foreach($primos as $numero) { 
 echo "$numero-"; 
 }   

Le falta:
1º Interacción
2º Guardado de la lista que te sugería antes.

Además cambia un poco con respecto a mi primer mensaje, ahora lo hice un poco más eficiente. De todas formas el principio es el mismo.


Saludos.

[gabyweb]

Ok gracias, sólo le faltan algunos ajustes y ya está. Lo pondré apenas me salga. Gracias por todo

[AlvaroG]

Solamente un comentario más, para aquellos que como yo estudien matémáticas: ya me di cuenta de que lo que puse en el primer mensaje no es completamente correcto, el 0 es compuesto y el 1 es el discutible (primo o ni primo ni compuesto).

Un comentario de un enfermito de los detalles


Saludos.

[ArrauKano]

recuerdo una q una vez tuve que hacer ese algoritmo para la u, pero ahora que lo mensionan, si les interesa evitarse el calculo, podrías hacer un cache de calculos, por ejemplo, supongamos que es la primera vez,
si el usuario pregunta por los 5 primeros primos, los calcular y guardar en un cache, se me ocurre una arreglo serializado en un archivo de texto. entonces si el usuario dp pregunta por los 4 primeros primos, se carga el cache y se depliega el resultado, si el usuario pide 8, calcula del sexto en adelante.

espero te ayude un poco mi idea, el algoritmo no es complicado, sol ohay que apegarse a la definicion de numero primo