Eratosthène algorithme de Sieve

Question

Je l'ai fait quelques recherches et n'a pas été en mesure de trouver des informations au sujet de cette mise en œuvre par rapport à tous les autres que je l'ai vu.

function sieve($top)
{
    for($i = 11; $i<$top; $i+=2)
    {
         if($i % 3 == 0 || $i % 5 == 0 
            ||  $i % 7 == 0)
          {
             continue;
          }
       echo "$i <br />";
   }
}

Ouais je sais juste imprime, mais ce n'est pas la partie importante. Quel est l'écueil majeur que ce soit le temps ou autre?

EDIT: Y at-il d'autres questions au-delà de l'évolutivité? Encore une fois Aussi merci pour les commentaires sur aller de l'avant avec la conclusion de premier choix.

Answer 1

L'écueil majeur de c'est ne pas à l'échelle. Une fois que les chiffres sont assez grand tout sera retourné. Vous liste des excluders module doit croître avec la recherche.

Answer 2

Vous pouvez consulter Sieve d'Eratosthène sur Wikipédia; et ce lien pour une implémentation PHP .

Answer 3

Il est limité aux nombres premiers jusqu'à 11. Pour étendre plus loin, vous devez ajouter || $u % 11 == 0 || $i % 13 == 0 ... etc

Answer 4

Tout d'abord, vous vérifiez que contre trois numéros (3, 7 et 11). Pour la Sieve de Erathosthenes, vous devriez commencer par une liste de numéros, 2..i. Puis boucle à travers cette liste, et supprimer les numéros qui sont des facteurs du numéro que vous itérer sur. Par exemple, une fois que vous obtenez à 7, qui est premier, vous devrez supprimer 49, 56, et d'autres multiples de 7.

En second lieu, la méthode que je viens de décrire escaladeraient très mal - si vous avez essayé la recherche de nombres premiers de 1..10 ^ 9, vous aurez besoin de 10 ^ 9 valeurs dans votre liste. Il existe d'autres moyens en plus de la Sieve de Erathosthenes pour trouver des nombres premiers - voir http://en.wikipedia.org / wiki / Prime_number

Answer 5

Cette utilisation de la fonction "Sieve d'Eratosthène algorithme"

function getPrimaryNumbers($n)
{
    $sieve = [];
    for($i = 1; $i <= $n; $i++) {
        $sieve[$i] = $i;
    } 

    $i =2;
    while($i * $i <= $n) {      
        if(isset($sieve[$i])) {
            $k = $i;
            while ($k * $i <= $n) {         
                unset($sieve[$k * $i]);
                $k++;
            }   
        }
    $i++;
    }           
    return $sieve;
}