About Taringa!

Popular channels

Como encontrar números primos PHP

Les traigo un simple script para encontrar los números primos hasta cierto valor.



El código está comentado para que se entienda.

<?php

//Empezamos a contar el tiempo de ejecución
$time_start microtime(true); 

function isPrime($num) {
    //1 no es primo. Ver: http://es.wikipedia.org/wiki/N%C3%BAmero_primo
    if($num == 1)
        return false;

    //2 es primo (el único número primo par)
    if($num == 2)
        return true;

    /**
     * Si el número es divisible por dos podemos descartar que sea primo*/
    if($num == 0) {
        return false;
    }

    /**
     * Chequeamos los números impares. Si alguno es un factor la función retorna falso.
     */
    for($i 3$i <= ceil(sqrt($num)); $i $i 2) {
        if($num $i == 0)
            return false;
    }

    return true;
}


//La variable max es el número mas alto a buscar
$max 1000000;
for (
$i=0$i $max $i++) { 
$test 
isPrime($i);
if (
$test == 1) {
$primos[] = $i;
}
}
/*Imprimimos los resultados incluyendo el tiempo de ejecución
Los resultados se muestran de la forma orden de resultado -> valor
*/
echo "<h2>Se buscaron números primos hasta el ".number_format($max,0,",",".")."<br>";
echo 
"Se encontraron ".number_format(count($primos),0,",",".")." números primos</h2> <br>";
//execution time of the script
$time_end microtime(true);

///Dividimos por 60 para obtener el tiempo en minutos
echo '<b><h3>Tiempo de ejecución:</b> '.($time_end $time_start).' segundos'."</h3><br>";
echo 
"<br>";
foreach (
$primos as $key => $value) {
echo (
$key+1)." -> ".number_format($value,0,",",".")."<br>";
}

El resultado es algo así:

Se buscaron números primos hasta el 100
Se encontraron 25 números primos

Tiempo de ejecución: 0.00018191337585449 segundos

1 -> 2
2 -> 3
3 -> 5
4 -> 7
5 -> 11
6 -> 13
7 -> 17
8 -> 19
9 -> 23
10 -> 29
11 -> 31
12 -> 37
13 -> 41
14 -> 43
15 -> 47
16 -> 53
17 -> 59
18 -> 61
19 -> 67
20 -> 71
21 -> 73
22 -> 79
23 -> 83
24 -> 89
25 -> 97
0No comments yet