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

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:

  1. WITH p1 AS (
  2. SELECT 2 AS p
  3. UNION ALL SELECT 3
  4. UNION ALL SELECT 5
  5. UNION ALL SELECT 7
  6. UNION ALL SELECT 11
  7. UNION ALL SELECT 13
  8. UNION ALL SELECT 17
  9. UNION ALL SELECT 19
  10. UNION ALL SELECT 23
  11. UNION ALL SELECT 29
  12. UNION ALL SELECT 31)
  13. , num10 AS (
  14. SELECT 0 AS n
  15. UNION ALL SELECT n+1
  16. FROM num10
  17. WHERE n<9)
  18. , num1000 AS (
  19. SELECT n1.n + 10*n2.n + 100*n3.n n
  20. FROM num10 n1, num10 n2, num10 n3)
  21. , np1000 AS (
  22. SELECT n
  23. FROM num1000, p1
  24. WHERE n%p = 0
  25. AND N>=P*P)
  26. SELECT *
  27. FROM num1000
  28. WHERE n NOT IN
  29. (SELECT n
  30. FROM np1000)
  31. AND n>1
  32. 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.

Dodaj komentarz

avatar
  Subscribe  
Powiadom o