Algorytmy szukające liczb pierwszych

Pracowite dzielenie

Funkcja find_primes() jest najbardziej primitywna (znalazła się tu tylko dla celów komparatystycznych). Mozolnie "szuka" ona w oreślonym przedziale ($from; $limit) liczb pierwszych testując każdą liczbę z tego przedziału, czyli sprawdzając, czy jest podzielna bez reszty przez jakąkolwiek inną liczbę z przedziału (2; $limit-1). Jedyne jej "usprytnienie" polega na wykorzystaniu zasady, mówiącej o tym, iż chcąc wykazać, że dana liczba jest pierwsza, wystarczy wziąć pod uwagę tylko te liczby pierwsze w ciągu liczb naturalnych, których kwadrat nie przewyższa tej liczby.

function find_primes($from, $limit) {
    if ($limit < 2) return false;
    if ($from < 3) {$primes_arr[] = 2; $from = 3;}
    for ($i = ($from%2 != 0) ? $from : $from+1; $i < $limit+1; $i+=2) {
        for ($n = 3, $p = true; $n < (int)(sqrt($i))+1; $n+=2)
            if ($i%$n == 0) {$p = false; break;}
        if ($p == true) $primes_arr[] = $i;
    }
    return !empty($primes_arr) ? $primes_arr : false;
}

Pracowite mnożenie

Funkcja left_primes() tworzy tablicę (2; $limit) i usuwa z niej wszystkie wielokrotności każdej kolejnej liczby z przedziału.

function left_primes($from, $limit) {
    if ($limit < 2) return false;
    for ($i = 1; $i <= $limit-1; $i++, $numbers_arr[$i] = true);
    for ($i = 2; $i <= $limit; $i++) {
        for ($n = $i*2; $n <= $limit; $n += $i) {
        unset($numbers_arr[$n]);
        }
    }
    if ($from > 2) for ($j = 2; $j < $from; $j++) unset($numbers_arr[$j]);
    $primes_arr = array_keys($numbers_arr);
    return !empty($primes_arr) ? $primes_arr : false;
}

Sito Eratostenesa (Sieve of Eratosthenes)

Po drobnej modyfikacji powyższego algorytmu otrzymamy funkcję sieve_primes() – klasyczne Sito Eratostenesa. Dzięki wykorzystaniu funkcji next() nie przemnaża ona niepotrzebnych (już wyeliminowanych) liczb.

function sieve_primes($from, $limit) {
    $numbers_arr = array_fill(2, $limit-1, true);
    for ($i = 2; $i < round(sqrt($limit))+1; next($numbers_arr)) {
        for ($i = key($numbers_arr), $n = $i*2; $n <= $limit; $n += $i) {
            unset($numbers_arr[$n]);
        }
    }
	if ($from > 2) for ($j = 2; $j < $from; $j++) unset($numbers_arr[$j]);
    return !empty($numbers_arr) ? array_keys($numbers_arr) : false;
}

Do stworzenia początkowej tablicy zamiast pętli for wykorzystana tu została prawie dwa razy szybszą funkcję array_fill(). Wbrew pozorom funkcja range() okazała się tylko kilkanaście procent szybsza od pętli i znacznie wolniejsza od array_fill().

Do usunięcia zbędnej części wyników najskuteczniejsza jest chyba pętla for, próby z array_slice(); okazały się gorsze pod względem wydajności.

Efekt działania funkcji sieve_primes() (sita Eratostenesa) wraz z interesującymi informacjami statystycznymi o zalezionych liczbach pirwszych można sprawdzić, wypełniając poniższy generator liczb pierwszych. Wartości zakresu muszą być liczbami naturalnymi z zakresu od 0 do 150000. To górne ograniczenie wynika z maksymalnej ilość pamięci dostępnej dla skryptów PHP na tym serwerze - tylko 16 MB - i ograniczenia maksymalnego czasu ich wykonywania do 8 sekund. Wadą algorytmów opartych na sicie Eratostenesa jest konieczność zaalokowania pamięci proporcjonalnej właśnie do górnego zakresu przeszukiwania (każda potencjalna liczba, czyli na początku cały zbiór liczb naturalnych z danego przedziału, to jedna para klucz-wartość w tablicy).

Statystyki dotyczące 664579 liczb pierwszych dla pierwszych 10 milionów liczb naturalnych można zobaczyć na tej stronie.

Silva Rerum

Algorytmy szukające liczb pierwszych

Pracowite dzielenie

Pracowite mnożenie

Sito Eratostenesa (Sieve of Eratosthenes)