Алгоритм сита Эратосфена

Question

Я провел некоторый поиск и не смог найти никакой информации относительно этой реализации по сравнению с любой другой, которую я видел.

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

Да, я знаю, что это просто распечатывает, но это не важная часть. Какая главная ловушка, будь то время или другое?

РЕДАКТИРОВАТЬ: Есть ли другие проблемы, кроме масштабируемости? Также еще раз спасибо за комментарии о продвижении вперед с основным поиском.

Answer 1

Главная ошибка в том, что она не масштабируется. Как только числа станут достаточно большими, все будет возвращено. Ваш список модулей исключения должен расти с поиском.

Answer 2

Вы можете сослаться на Сито Эратосфена в Википедии; и эта ссылка для реализации PHP.

Answer 3

Эта функция использует "Алгоритм сита Эратосфена"

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;
}

Answer 4

Во-первых, вы проверяете только по трем числам (3, 7 и 11). Для Сита Эратхофена вы должны начать со списка чисел, 2..i. Затем переберите этот список и удалите числа, которые являются факторами числа, которое вы повторяете. Например, как только вы доберетесь до 7, которое является простым, вам нужно убрать 49, 56 и другие кратные 7.

Во-вторых, метод, который я только что описал, очень плохо масштабируется - если вы попытаетесь найти простые числа из 1..10 ^ 9, вам понадобится 10 ^ 9 значений в вашем списке. Есть и другие способы, кроме решета Эратхофена, найти простые числа - см. http://en.wikipedia.org/wiki/Prime_number

Answer 5

Оно ограничено простыми числами до 11. Чтобы еще больше его расширить, вам нужно добавить || $u % 11 == 0 || $i % 13 == 0 ... и т.