Foros del Web » Programación web » PHP »

Generar los "n" primeros numeros primos

Estas en el tema de Generar los "n" primeros numeros primos en el foro de PHP en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 05/03/2006, 09:34
Avatar de gabyweb  
Fecha de Ingreso: enero-2002
Ubicación: Lima
Mensajes: 364
Antigüedad: 12 años, 6 meses
Puntos: 0
Generar los "n" primeros numeros primos

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
__________________
Gaby :adios:
  #2 (permalink)  
Antiguo 05/03/2006, 10:41
Avatar de AlvaroG
/bin/env python
 
Fecha de Ingreso: julio-2005
Ubicación: Canelones, Uruguay
Mensajes: 7.621
Antigüedad: 9 años
Puntos: 586
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.
__________________
blog ElCodiguero
  #3 (permalink)  
Antiguo 05/03/2006, 10:58
Avatar de AlvaroG
/bin/env python
 
Fecha de Ingreso: julio-2005
Ubicación: Canelones, Uruguay
Mensajes: 7.621
Antigüedad: 9 años
Puntos: 586
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 == ) {
  
$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.
__________________
blog ElCodiguero
  #4 (permalink)  
Antiguo 05/03/2006, 11:16
Avatar de gabyweb  
Fecha de Ingreso: enero-2002
Ubicación: Lima
Mensajes: 364
Antigüedad: 12 años, 6 meses
Puntos: 0
Estoy tratando de probar tu codigo y no me muestra nada
__________________
Gaby :adios:
  #5 (permalink)  
Antiguo 05/03/2006, 11:19
Avatar de AlvaroG
/bin/env python
 
Fecha de Ingreso: julio-2005
Ubicación: Canelones, Uruguay
Mensajes: 7.621
Antigüedad: 9 años
Puntos: 586
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";
 } 
__________________
blog ElCodiguero
  #6 (permalink)  
Antiguo 05/03/2006, 11:23
Avatar de gabyweb  
Fecha de Ingreso: enero-2002
Ubicación: Lima
Mensajes: 364
Antigüedad: 12 años, 6 meses
Puntos: 0
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
__________________
Gaby :adios:
  #7 (permalink)  
Antiguo 05/03/2006, 11:47
Avatar de AlvaroG
/bin/env python
 
Fecha de Ingreso: julio-2005
Ubicación: Canelones, Uruguay
Mensajes: 7.621
Antigüedad: 9 años
Puntos: 586
Bueno, revisado y funcionando.


Código PHP:
<?php 
# $actual es el número que estoy revisando (comienza por $n) 

$n 100;
$primos = array(123);

for (
$actual 4$actual <= $n$actual++) { 

for (
$div 2$div <= (($actual 2) + 1); $div++) { 
 if ( 
$actual $div == ) { 
  
$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.
__________________
blog ElCodiguero
  #8 (permalink)  
Antiguo 05/03/2006, 11:58
Avatar de gabyweb  
Fecha de Ingreso: enero-2002
Ubicación: Lima
Mensajes: 364
Antigüedad: 12 años, 6 meses
Puntos: 0
Ok gracias, sólo le faltan algunos ajustes y ya está. Lo pondré apenas me salga. Gracias por todo
__________________
Gaby :adios:
  #9 (permalink)  
Antiguo 05/03/2006, 17:53
Avatar de AlvaroG
/bin/env python
 
Fecha de Ingreso: julio-2005
Ubicación: Canelones, Uruguay
Mensajes: 7.621
Antigüedad: 9 años
Puntos: 586
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.
__________________
blog ElCodiguero
  #10 (permalink)  
Antiguo 05/03/2006, 20:41
 
Fecha de Ingreso: noviembre-2002
Ubicación: Santiago
Mensajes: 663
Antigüedad: 11 años, 8 meses
Puntos: 4
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
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Tema Cerrado

SíEste tema le ha gustado a 1 personas (incluyéndote)




La zona horaria es GMT -6. Ahora son las 16:54.
SEO by vBSEO 3.3.2