I_P_W14_M03 Czy liczba jest liczbą pierwszą?
Choć z pojęciem algorytmu spotykasz się najczęściej na lekcjach informatyki, nie znaczy to, że algorytmy nie mogą być wykorzystywane do rozwiązywania problemów z innych dziedzin.
Algorytmy stosowane do rozwiązywania problemów matematycznych za pomocą operacji na liczbach nazywamy algorytmami liczbowymi lub numerycznymi.
Jednym z problemów, który możemy rozwiązać, wykorzystując algorytmy liczbowe, jest sprawdzenie, czy dana liczba spełnia określone warunki.
Na lekcjach matematyki nauczyliśmy się, jak definiować liczby pierwsze czy liczby doskonałe. Wiemy zatem, że są to liczby, które spełniają określone warunki. To, czy dana liczba należy do konkretnego zbioru, weryfikujemy, korzystając z odpowiedniego algorytmu liczbowego.
Ćwiczenie na rozgrzewkę.
Czy potrafisz wymienić wszystkie liczby pierwsze od 1 do 100? Sprawdź, jak ci poszło, analizując poniższy diagram.
Czy wiesz, że algorytmy oparte na liczbach pierwszych są fundamentem bezpieczeństwa w internecie? Wiele systemów szyfrowania, takich jak RSA, wykorzystuje fakt, że bardzo trudno jest rozłożyć dużą liczbę na czynniki pierwsze. Choć sprawdzenie, czy liczba jest pierwsza, jest stosunkowo proste, to odwrotna operacja — faktoryzacja — staje się ekstremalnie trudna dla bardzo dużych liczb. To właśnie ta „trudność” chroni Twoje dane podczas zakupów online, logowania do banku czy wysyłania wiadomości.
Wyjaśnisz, jakie właściwości musi posiadać dana liczba, aby mogła zostać nazwana liczbą pierwszą.
Przeanalizujesz algorytmy, które pozwalają sprawdzić, czy dana liczba jest liczbą pierwszą.
Zapiszesz algorytm w języku Python testujący czy dana liczba jest liczbą pierwszą.