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.
