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:
