Jak rozpoznać czy liczba naturalna jest pierwsza?
Aby sprawdzić, czy liczba naturalna jest liczbą pierwszą, należy dzielić ją kolejno przez wszystkie liczby mniejsze od niej z wyjątkiem jedynki. Jeśli przy każdym dzieleniu reszta z dzielenia jest różna od zera, to liczba jest liczbą pierwszą. Natomiast jeżeli choć jedno dzielenie daje resztę równą zero, to sprawdzana liczba naturalna jest liczbą złożoną. Nie jest to więc problem teoretyczny, jednak praktycznie trudny w przypadku bardzo dużych liczb.
Jeśli liczba jest stosunkowo niewielka, takie dzielenia możemy przeprowadzić sami, natomiast jeśli liczba nie jest już mała, to rozsądnie jest sprawdzić ją za pomocą urządzenia, które potocznie nazywa się komputerem. Ale ów maszynę trzeba zaprogramować, czyli napisać algorytm, który rozstrzygnie czy dana liczba jest pierwsza. Algorytm ten musi być przy tym efektywny, taki który wykona możliwie jak najmniej operacji, w jak najkrótszym czasie. algorytm >>
