Menu Zamknij

Pozostałe algorytmy

Sprawdzanie czy liczba jest liczbą pierwszą

W pierwszej kolejności algorytm sprawdza czy wprowadzona przez nas liczba jest dwójką. Liczba 2 stanowi wyjątek – musimy ją sprawdzić, ponieważ jest to jedyna liczba pierwsza, która jest parzysta. Jeśli to dwójka, to liczba jest pierwsza.

if n % 2 == 0 or n <= 1 – jeśli liczba jest parzysta lub mniejsza bądź równa 1, to na pewno nie jest pierwsza.

W kolejnym kroku algorytm sprawdza, czy nasza liczba posiada dzielniki. Jeśli posiada, to nie jest to liczba pierwsza.

Później nasz algorytm sprawdza dzielniki z przedziału [3,⌊√n⌋+1), gdzie ⌊√n⌋ to pierwiastek z n zaokrąglony w dół (tzw. podłoga).

Algorytm mógłby sprawdzać dzielniki z większego przedziału [3,n), jednak jest to nadmiarowy przedział który jedynie powodowałby dłuższą pracę algorytmu, zwłaszcza przy wprowadzaniu większych liczb.

Przedział ten wziął sie z tego iż dzielniki zawsze występują parami. Każdy dzielnik z przedziału [3,⌊√n⌋+1) będzie odpowiadał jednemu z przedziału [⌊√n⌋+1,n). Można więc zatem sprawdzić w algorytmie jedynie dzielniki z przedziału [3,⌊√n⌋+1).

NWD

Największy wspólny dzielnik (NWD) dla dwóch liczb jest to największa liczba naturalna, która dzieli każdą z tych liczb bez reszty.

Na przykład dla 18 i 24, największą liczbą naturalną która dzieli te dwie liczby bez reszty jest 6. Dla liczb 8 i 20 jest to 4.

Algorytm obliczający NWD możemy przedstawić w wersji iteracyjnej jak i rekurencyjnej:

W wersji iteracyjnej pętla while b: wykonuje się tak długo, jak b jest większe od 0.

NWW

Najmniejsza wspólna wielokrotność (NWW) dwóch liczb naturalnych jest to najmniejsza liczba naturalna której dzielnikami są obie te liczby.

Na przykład dla liczb 4 i 5 jest to 20, bo 20 jest najmniejszą liczbą naturalną, której dzielnikami są liczby 4 i 5.

Dla liczb 3 i 10 jest to 30, bo 30 jest najmniejszą liczbą naturalną, która jest podzielna zarówno przez 3, jak i przez 10.

NWW dwóch liczb najprościej jest obliczyć, znając ich NWD. Korzystamy wtedy z następującego wzoru:

Mając zdefiniowaną wcześniej funkcję obliczającą NWD, funkcję znajdującą NWW możemy zapisać w Pythonie w następujący sposób:

Rozkład liczby na czynniki pierwsze

Czynnik pierwszy jest to dowolna liczba pierwsza, która dzieli bez reszty naturalną liczbę złożoną. Ten algorytm można przedstawić w następujący sposób: