PHP: Números Primos

Muy buenas lechugas de mi corazón,

Hoy os traigo algo que no es que sea especialmente útil, pero a mi me gusta.

Estaba yo dando un vistazo por lawebdelprogramador.com y me encontré este código. Algo que más o menos hemos hecho todos nuestros inicios.

Así que me salió la vena sentimental, además de que soy un fan de los números primos (me gustan, no se porqué ^^) y he querido mostrarlo aquí para que lo veáis vosotros.

[sourcecode lang=”php”]
<?php
for ($i = 1; $i <= 100; $i++)
{
if (primo($i))
echo "El número " . $i . " es primo";
else
echo "El número " . $i . " NO es primo";
}

/**
* Función que determina si un numero es primo
* Tiene que recibir el numero a determinar si es primo o no
* Devuelve True o False
*/
function primo($num)
{
$cont = 0;

// Funcion que recorre todos los numero desde el 2 hasta el valor recibido
for ($i = 2; $i <= $num; $i++)
{
if ($num % $i == 0)
{
# Si se puede dividir por algun numero mas de una vez, no es primo
if (++$cont > 1)
return false;
}
}

return true;
}
?>
[/sourcecode]

Lo único, es que el conozca un poco estos números, sabrá que para saber si x es un número primo, no hace falta buscar sus divisores desde 2 hasta X.

Si os fijais, todos los números superiores a x/2 no serán divisores de x. Por lo tanto ya nos ahorramos la mitad de camino.

Pero todavía podemos ahorra algo más de camino, ya que si se busca hasta ((raiz cuadrada de x) + 1) y no se encuentra un divisor, es que ese número es primo.

Espero que os guste ^_^

Deja un comentario