Jak rozpoznać czy liczba naturalna jest pierwsza?
Aby sprawdzić, czy liczba naturalna jest liczbą pierwszą, należy dzielić ją kolejno przez wszystkie liczby większe od $1$ i mniejsze równe pierwiastka kwadratowego z tej liczby. 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 można ją sprawdzić z pomocą komputera. 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. algorytm >>