Algorytm sprawdzania czy liczba jest pierwsza istnieje, ale jego złożoność jest wykładnicza, więc przy naprawdę dużych liczbach pierwszych można go sobie w buty wsadzić.
@pcmn: bajki opowiadasz, są testy deterministyczne działające w wielomianowym czasie, a w praktyce często używa się testów probabilistycznych, np. test Millera - Rabina, np. w implementacji openssl.
Inna sprawa, że w artykule chodzi o znajomość algorytmów na poziomie wczesnej gimbazy (wykaz algorytmów z CKE), a opisany w artykule jest do tego odpowiedni.
Będąc w gimnazjum 12 lat temu staraliśmy się tym algorytmem policzyć liczbę pierwszą z 25 tys cyfr. Obecnie możesz dostać dużą kasę za liczbę która posiada około 100 tys cyfr, ale musisz sprawdzić, nie jestem już na bieżąco.
Komentarze (8)
najlepsze
Inna sprawa, że w artykule chodzi o znajomość algorytmów na poziomie wczesnej gimbazy (wykaz algorytmów z CKE), a opisany w artykule jest do tego odpowiedni.
Jak na kogoś kto pisze do obcego człowieka "bajki opowiadasz" jesteś nad wyraz wrażliwy. A ja zwykłem odpłacać pięknym za nadobne.
"Dla odpowiedniej liczby prób" sito Eratostenesa też jest wystarczające.
Będąc w gimnazjum 12 lat temu staraliśmy się tym algorytmem policzyć liczbę pierwszą z 25 tys cyfr. Obecnie możesz dostać dużą kasę za liczbę która posiada około 100 tys cyfr, ale musisz sprawdzić, nie jestem już na bieżąco.
Tutaj masz