Jak rozpoznać czy liczba naturalna jest pierwsza?
Aby sprawdzić, czy liczba naturalna n jest liczbą pierwszą, należy dzielić ją kolejno przez wszystkie liczby mniejsze od niej. Jeśli przy każdym dzieleniu reszta z dzielenia jest różna od zera, to liczba n jest liczbą pierwszą. Natomiast jeżeli choć jedno dzielenie daje resztę równą zero, to liczba naturalna n 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 >>
Poniżej możesz sprawdzić czy liczba naturalna (1 < n < 10000000) jest pierwsza.