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.
@sok:
Koteczku, test M-R daje wynik PRAWDOPODOBNY.
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 wszytko.
https://primes.utm.edu/largest.html
Ja się w ten sposób uczyłem programować ;)