Check the new version here

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
0
0
0
0No comments yet