Eratosthenes Algoritma Elek

4 Cevap php

Bazı arama yaptım ve gördüğüm her biri karşı bu uygulamaya ilişkin herhangi bir bilgi bulmak mümkün değildi.

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

Evet, ben sadece bunu yazdıran biliyorum, ama bu önemli bir parçası değil. O zaman ya da başka olsun büyük tuzak nedir?

EDIT: ölçeklenebilirlik ötesinde başka sorunlar var mı? Ayrıca yine ana bulgu ile ilerlemeye hakkında yorumlar için teşekkürler.

4 Cevap

Bu büyük hatadır bu ölçek değildir olduğunu. Sayılar yeterince büyük bir kez bir şey iade edilecektir. Modülü excluders Seni listesi arama ile büyümeye ihtiyacı var.

11'e kadar asal sayıların sınırlı bulunuyor. Başka size || $u % 11 == 0 || $i % 13 == 0 ... vb eklemek gerekir uzatmak için

Wikipedia'da Sieve of Eratosthenes başvurabilirsiniz; ve this link, bir PHP uygulama için.

Öncelikle, sadece üç sayı (3, 7, ve 11) karşı kontrol ediyoruz. Erathosthenes ve eleği, i .. sayılar, 2 listesi ile başlamalıdır. Sonra bu listesinde döngü ve üzerinde yineleme konum sayısının faktörlerdir numaralarını kaldırmak. Eğer asal 7'ye kez olsun Örneğin, sen 49, 56 kaldırmak gerekir, ve 7 diğer katları.

İkincisi, ben sadece açıklanan yöntem çok kötü ölçek ederim - 10 ^ 9 .. 1'den asal arıyor çalıştı, listenizdeki 10 ^ 9 değerleri gerekiyordu. Asal sayıları bulmak için Erathosthenes süzgecinden dışında başka yolları vardır - bkz http://en.wikipedia.org/wiki/Prime%5Fnumber

etiketler