Pchełki SQL, odcinek 9: Tysiąc pierwszych pierwszych

https://xpil.eu/XfTiz 📋

A konkretnie rzecz mówiąc, pierwsze mniejsze od tysiąca - o tym będzie dzisiejsza pchełka SQL. Pokażę w jaki sposób wygenerować (za pomocą SQL) wszystkie liczby pierwsze mniejsze niż 1000.

Jak już kiedyś wspominałem, używanie wysokopoziomowego języka zapytań do przeprowadzania obliczeń numerycznych to trochę jakby wiązać sznurówki nożem i widelcem. Da się, ale niezbyt szybko, niezbyt porządnie, i trzeba się sporo natrudzić.

No to lecimy. Najpierw kod, potem objaśnienia.

Kod:

with p1 as (
select 2 as p
union all select 3
union all select 5
union all select 7
union all select 11
union all select 13
union all select 17
union all select 19
union all select 23
union all select 29
union all select 31)
, num10 as (
select 0 as n
union all select n+1
from num10
where n<9)
, num1000 as (
select n1.n + 10*n2.n + 100*n3.n n
from num10 n1, num10 n2, num10 n3)
, np1000 as (
select n
from num1000, p1
where n%p = 0
and N>=P*P)
select *
from num1000
where n not in
(select n
from np1000)
and n>1
order by 1;

Objaśnienia:

with p1 as ...

Tutaj podajemy (ręcznie) wszystkie liczby pierwsze od 2 do 31. Dlaczego 31 a nie na przykład 47? Ponieważ 31 jest największą liczbą pierwszą, której kwadrat jest mniejszy od tysiąca.

, num10 as ...

Tu generujemy liczby całkowite od 0 do 9

, num1000 as ...

Tutaj z kolei generujemy wszystkie liczby całkowite od 0 do 999, używając iloczynu kartezjańskiego trzech kopii poprzedniego num10

, np1000 as ...

Tutaj generujemy wszystkie liczby niepierwsze (czyli złożone) mniejsze od 1000. Metoda polega na wyłapaniu wszystkich liczb, które podzielone przez którąkolwiek z liczb pierwszych od 2 do 31 dadzą w wyniku resztę zero (operator % zwraca resztę z dzielenia, czyli n%p to reszta z dzielenia n przez p, n pochodzi z num1000, p pochodzi z p1).

Na szczególną uwagę zasługuje tutaj warunek N >= P * P. Skąd takie coś? Otóż N >= P * P jest arytmetycznie tożsame z P <= SQRT(N) - jak wiadomo, sprawdzając pierwszość liczby, wystarczy spróbować podzielić ją przez wszystkie liczby pierwsze mniejsze od pierwiastka z liczby sprawdzanej (wyjątkiem są kwadraty liczb pierwszych - tu trzeba sprawdzić mniejsze lub równe). Znacznie ogranicza to ilość dzieleń. Przy ogromnych liczbach algorytm ten nie sprawdza się zupełnie, jednak tutaj mamy liczby maksymalnie trzycyfrowe, więc taka metoda w zupełności wystarczy.

Wreszcie ostatnie zapytanie wybiera wszystkie liczby większe od jedynki, których nie ma w np1000. Są to liczby pierwsze.

Stosowalność powyższej pchełki w życiu codziennym jest znikoma. Już prędzej zacznę wiązać krawat dziadkiem do orzechów... Ale jako ciekawostka na bloga nadaje się idealnie.

https://xpil.eu/XfTiz 📋