Primorial sieve
: 12 cze 2024, o 12:18
Zasada działania tego sposobu przesiewania liczb pierwszych, jest na tyle prosta, że powinien ją zrozumieć uczeń szkoły średniej.
Badaną liczbę \(\displaystyle{ n}\) (a w zasadzie kolejne, badane na prymarność liczby), dzielimy przez liczbę testową \(\displaystyle{ q}\), stanowiącą primorial dużej liczby pierwszej \(\displaystyle{ p}\): im większe \(\displaystyle{ p}\), tym lepiej. W efekcie otrzymujemy pewną liczbę \(\displaystyle{ m}\), która nas tutaj za bardzo nie interesuje, a która mówi nam, ile razy \(\displaystyle{ q}\) mieści się w \(\displaystyle{ n}\). Dla samej metody nie jest to wartość istotna.
Ważna jest dla nas reszta z dzielenia, czyli kongruencja liczby \(\displaystyle{ n}\), wobec \(\displaystyle{ q}\).
\(\displaystyle{ n (\bmod q) ≡ r}\)
Jeżeli \(\displaystyle{ r}\) jest liczbą pierwszą, taką że, jest większe od największego ze składników składających się na \(\displaystyle{ q }\)(przypominam, że \(\displaystyle{ q}\) jest iloczynem kolejnych liczb pierwszych, i jest oczywiście liczbą złożoną), czyli jest większe od \(\displaystyle{ p}\) — to badane \(\displaystyle{ n}\) ma duże szanse być liczbą pierwszą. Tylko i wyłącznie w tym przypadku: to znaczy pozostałe możliwości wskazują jednoznacznie, z całkowitą pewnością, na to, że Liczba \(\displaystyle{ n}\) jest liczbą złożoną.
Gdy \(\displaystyle{ r}\) jest mniejsze od \(\displaystyle{ p}\), to nawet gdy jest liczbą pierwszą, to dzieli się przez których ze składników liczby \(\displaystyle{ q}\). A w takim razie, przez ten składnik dzieli się zarówno reszta z dzielenia, jak i samo \(\displaystyle{ q}\). Więc suma ta również się przez ten składnik dzieli. Ujmijmy to w równaniu:
\(\displaystyle{ n = mq + r}\)
Gdzie \(\displaystyle{ q}\) oczywiście dzieli się przez WSZYSTKIE składniki tworzące ten \(\displaystyle{ primorial}\). Jeżeli teraz \(\displaystyle{ r}\) dzieli się przez dowolny z tych składników — to liczba \(\displaystyle{ n}\) żadną miarą nie może być pierwsza, to chyba jasne... A to zachodzi dla wszystkich \(\displaystyle{ r}\) złożonych, a \(\displaystyle{ nie}\) zachodzi tylko dla liczb pierwszych, większych od \(\displaystyle{ p}\).
Aby powyższe zilustrować praktycznie, weźmy za \(\displaystyle{ p}\) liczbę pierwszą 7.
\(\displaystyle{ 7\#= 210}\)
Mamy dowolny n taki że:
\(\displaystyle{ n (\bmod 210) \equiv r}\) czyli \(\displaystyle{ n = mq + r}\)
Gdzie \(\displaystyle{ r}\) jest mniejsze od \(\displaystyle{ 210}\). Jeżeli \(\displaystyle{ r}\) jest liczbą złożoną, to dzieli się przez któryś ze składników tworzących \(\displaystyle{ q}\), więc przez ten składnik dzieli się również liczba \(\displaystyle{ n}\), czyli nie może być liczbą pierwszą. Jeżeli \(\displaystyle{ r}\) jest liczbą pierwszą, ale mniejszą niż \(\displaystyle{ p}\), lub równą \(\displaystyle{ p}\), wówczas \(\displaystyle{ n}\) dzieli się przez \(\displaystyle{ r}\) — i oczywiście też liczbą pierwszą nie jest.
W zakresie od \(\displaystyle{ 1}\), do \(\displaystyle{ 210}\) — jest \(\displaystyle{ 46}\) liczb pierwszych, ale odrzucamy cztery z nich, ponieważ są mniejsze, lub równe \(\displaystyle{ 7}\). Oczywiście jeśli \(\displaystyle{ r}\) jest równe \(\displaystyle{ 1}\), to liczba \(\displaystyle{ n}\) może być liczbą pierwszą.
\(\displaystyle{ \frac{43}{210} =20,476\% }\) tych liczb wskazuje na możliwość że \(\displaystyle{ n}\) jest liczbą pierwszą, czyli odpada nam \(\displaystyle{ 79,524\%}\) śmiecia.
Gdy p będziemy wybierać jeszcze większe, selekcja będzie jeszcze wydajniejsza:
Dla \(\displaystyle{ p}\) równego \(\displaystyle{ 11}\) mamy \(\displaystyle{ 11\#=2\ 310}\) a w tym przedziale znajdują się 343 liczby pierwsze, minus 4, pozostaje 339, więc już tylko \(\displaystyle{ 14,675\%}\) liczb z tego przedziału będzie liczbami pierwszymi, zaś \(\displaystyle{ 85,325\%}\) to liczby ewidentnie złożone.
Dla \(\displaystyle{ p}\) równego \(\displaystyle{ 13}\) mamy \(\displaystyle{ 13\#=30\ 030}\) skąd otrzymujemy \(\displaystyle{ (3248 - 6)}\) liczb pierwszych spełniających odpowiednie warunki, co stanowi \(\displaystyle{ 10,796\%}\) wskazań pozytywnych, zaś \(\displaystyle{ 89,204\%}\) to liczby złożone, czyli odpad produkcyjny.
Widać więc wyraźnie, że wydajność wskazań rośnie wraz ze wzrostem liczby \(\displaystyle{ p}\), przy czym wzrost ten jest coraz powolniejszy, ale stały, i nie zanikający...
W podsumowaniu zestawmy te wartości:
\(\displaystyle{ 7}\) → wyklucza \(\displaystyle{ 79,524\%}\) liczb jako ewidentnie złożone
\(\displaystyle{ 11}\) → eliminuje \(\displaystyle{ 85,325\%}\) liczb. \(\displaystyle{ Δ}\) wzrostu wynosi \(\displaystyle{ 5,801\%}\)
\(\displaystyle{ 13}\) → rozpoznaje \(\displaystyle{ 89,204\%}\) liczb — jako złożone. \(\displaystyle{ Δ}\) wzrostu \(\displaystyle{ 3,879\%}\) — widać, że wzrost jest coraz powolniejszy…
Metoda stanowi skrzyżowanie idei zawartej w konstrukcji szeregów Dirichleta, z zasadą działania sita Eratostenesa, natomiast należy odnotować z naciskiem, że w porównaniu z innymi metodami badania prymarności, jest metodą o wyjątkowo niskiej złożoności obliczeniowej, można powiedzieć, że wręcz znikomej...
Suplement
\(\displaystyle{ 2\#}\) → wyklucza \(\displaystyle{ 50,0\%}\) liczb jako ewidentnie złożone
\(\displaystyle{ 3\#}\) → wyklucza \(\displaystyle{ 66,667\%}\) liczb — są złożone. \(\displaystyle{ Δ}\) wzrostu \(\displaystyle{ 16,667\%}\)
\(\displaystyle{ 5\# =30}\) → wyklucza \(\displaystyle{ (1-(7/30))\cdot100\%=76,667\%}\) liczb — są złożone. \(\displaystyle{ Δ}\) wzrostu \(\displaystyle{ 10,0\%}\)
Badaną liczbę \(\displaystyle{ n}\) (a w zasadzie kolejne, badane na prymarność liczby), dzielimy przez liczbę testową \(\displaystyle{ q}\), stanowiącą primorial dużej liczby pierwszej \(\displaystyle{ p}\): im większe \(\displaystyle{ p}\), tym lepiej. W efekcie otrzymujemy pewną liczbę \(\displaystyle{ m}\), która nas tutaj za bardzo nie interesuje, a która mówi nam, ile razy \(\displaystyle{ q}\) mieści się w \(\displaystyle{ n}\). Dla samej metody nie jest to wartość istotna.
Ważna jest dla nas reszta z dzielenia, czyli kongruencja liczby \(\displaystyle{ n}\), wobec \(\displaystyle{ q}\).
\(\displaystyle{ n (\bmod q) ≡ r}\)
Jeżeli \(\displaystyle{ r}\) jest liczbą pierwszą, taką że, jest większe od największego ze składników składających się na \(\displaystyle{ q }\)(przypominam, że \(\displaystyle{ q}\) jest iloczynem kolejnych liczb pierwszych, i jest oczywiście liczbą złożoną), czyli jest większe od \(\displaystyle{ p}\) — to badane \(\displaystyle{ n}\) ma duże szanse być liczbą pierwszą. Tylko i wyłącznie w tym przypadku: to znaczy pozostałe możliwości wskazują jednoznacznie, z całkowitą pewnością, na to, że Liczba \(\displaystyle{ n}\) jest liczbą złożoną.
Gdy \(\displaystyle{ r}\) jest mniejsze od \(\displaystyle{ p}\), to nawet gdy jest liczbą pierwszą, to dzieli się przez których ze składników liczby \(\displaystyle{ q}\). A w takim razie, przez ten składnik dzieli się zarówno reszta z dzielenia, jak i samo \(\displaystyle{ q}\). Więc suma ta również się przez ten składnik dzieli. Ujmijmy to w równaniu:
\(\displaystyle{ n = mq + r}\)
Gdzie \(\displaystyle{ q}\) oczywiście dzieli się przez WSZYSTKIE składniki tworzące ten \(\displaystyle{ primorial}\). Jeżeli teraz \(\displaystyle{ r}\) dzieli się przez dowolny z tych składników — to liczba \(\displaystyle{ n}\) żadną miarą nie może być pierwsza, to chyba jasne... A to zachodzi dla wszystkich \(\displaystyle{ r}\) złożonych, a \(\displaystyle{ nie}\) zachodzi tylko dla liczb pierwszych, większych od \(\displaystyle{ p}\).
Aby powyższe zilustrować praktycznie, weźmy za \(\displaystyle{ p}\) liczbę pierwszą 7.
\(\displaystyle{ 7\#= 210}\)
Mamy dowolny n taki że:
\(\displaystyle{ n (\bmod 210) \equiv r}\) czyli \(\displaystyle{ n = mq + r}\)
Gdzie \(\displaystyle{ r}\) jest mniejsze od \(\displaystyle{ 210}\). Jeżeli \(\displaystyle{ r}\) jest liczbą złożoną, to dzieli się przez któryś ze składników tworzących \(\displaystyle{ q}\), więc przez ten składnik dzieli się również liczba \(\displaystyle{ n}\), czyli nie może być liczbą pierwszą. Jeżeli \(\displaystyle{ r}\) jest liczbą pierwszą, ale mniejszą niż \(\displaystyle{ p}\), lub równą \(\displaystyle{ p}\), wówczas \(\displaystyle{ n}\) dzieli się przez \(\displaystyle{ r}\) — i oczywiście też liczbą pierwszą nie jest.
W zakresie od \(\displaystyle{ 1}\), do \(\displaystyle{ 210}\) — jest \(\displaystyle{ 46}\) liczb pierwszych, ale odrzucamy cztery z nich, ponieważ są mniejsze, lub równe \(\displaystyle{ 7}\). Oczywiście jeśli \(\displaystyle{ r}\) jest równe \(\displaystyle{ 1}\), to liczba \(\displaystyle{ n}\) może być liczbą pierwszą.
\(\displaystyle{ \frac{43}{210} =20,476\% }\) tych liczb wskazuje na możliwość że \(\displaystyle{ n}\) jest liczbą pierwszą, czyli odpada nam \(\displaystyle{ 79,524\%}\) śmiecia.
Gdy p będziemy wybierać jeszcze większe, selekcja będzie jeszcze wydajniejsza:
Dla \(\displaystyle{ p}\) równego \(\displaystyle{ 11}\) mamy \(\displaystyle{ 11\#=2\ 310}\) a w tym przedziale znajdują się 343 liczby pierwsze, minus 4, pozostaje 339, więc już tylko \(\displaystyle{ 14,675\%}\) liczb z tego przedziału będzie liczbami pierwszymi, zaś \(\displaystyle{ 85,325\%}\) to liczby ewidentnie złożone.
Dla \(\displaystyle{ p}\) równego \(\displaystyle{ 13}\) mamy \(\displaystyle{ 13\#=30\ 030}\) skąd otrzymujemy \(\displaystyle{ (3248 - 6)}\) liczb pierwszych spełniających odpowiednie warunki, co stanowi \(\displaystyle{ 10,796\%}\) wskazań pozytywnych, zaś \(\displaystyle{ 89,204\%}\) to liczby złożone, czyli odpad produkcyjny.
Widać więc wyraźnie, że wydajność wskazań rośnie wraz ze wzrostem liczby \(\displaystyle{ p}\), przy czym wzrost ten jest coraz powolniejszy, ale stały, i nie zanikający...
W podsumowaniu zestawmy te wartości:
\(\displaystyle{ 7}\) → wyklucza \(\displaystyle{ 79,524\%}\) liczb jako ewidentnie złożone
\(\displaystyle{ 11}\) → eliminuje \(\displaystyle{ 85,325\%}\) liczb. \(\displaystyle{ Δ}\) wzrostu wynosi \(\displaystyle{ 5,801\%}\)
\(\displaystyle{ 13}\) → rozpoznaje \(\displaystyle{ 89,204\%}\) liczb — jako złożone. \(\displaystyle{ Δ}\) wzrostu \(\displaystyle{ 3,879\%}\) — widać, że wzrost jest coraz powolniejszy…
Metoda stanowi skrzyżowanie idei zawartej w konstrukcji szeregów Dirichleta, z zasadą działania sita Eratostenesa, natomiast należy odnotować z naciskiem, że w porównaniu z innymi metodami badania prymarności, jest metodą o wyjątkowo niskiej złożoności obliczeniowej, można powiedzieć, że wręcz znikomej...
Suplement
\(\displaystyle{ 2\#}\) → wyklucza \(\displaystyle{ 50,0\%}\) liczb jako ewidentnie złożone
\(\displaystyle{ 3\#}\) → wyklucza \(\displaystyle{ 66,667\%}\) liczb — są złożone. \(\displaystyle{ Δ}\) wzrostu \(\displaystyle{ 16,667\%}\)
\(\displaystyle{ 5\# =30}\) → wyklucza \(\displaystyle{ (1-(7/30))\cdot100\%=76,667\%}\) liczb — są złożone. \(\displaystyle{ Δ}\) wzrostu \(\displaystyle{ 10,0\%}\)