Matematyka.pl

Witam
Jak można udowodnić czy jakaś liczba jest pierwsza czy złożona? CHodzi mi o duże liczby conajmniej złożone z kilkudziesięciu cyfr.

Cechy podzielności tutaj chyba nie pomogą. Próbowałem również programami ale coś nie wyszło. Mam nadzieje że wyraziłem się dosyć jasno

... zo%C5%9Bci
zajrzyj tutaj

więc jeżeli chodzi o te algorytmy, to mój komp jest za słaby żeby sprawdzić czy liczba zlożona z kilkudziesięciu cyfr jest pierwsza czy złożona. Chyba że ty masz dobry sprzęt...

hmm. może skorzystaj z tego że liczba "p" jest pierwsza gdy zachodzi :
\(\displaystyle{ p|(p-1)!+1}\)

111..122...2111...1 + 6 więc co z tą liczbą?
(14) ..(7) ..... (14)

w nawiasach pod liczbami napisałem z ilu cyf się składa, więc odpowiendnio 14 "jedynek" 7"dwójek" 14"jedynek + 6

Podzielne przez \(\displaystyle{ 3}\)

Cóż, ten pomysł z odwróceniem tw Wilsona jest raczej kiepski, bo obliczanie silni z liczby mającej kilkadziesiąt cyfr, a potem sprawdzanie czy się przez coś dzieli może trochę potrwać.

Ja tam się nie znam, ale patrząc na to czym chwali się wikipedia, to algorytm o złożoności \(\displaystyle{ O\left((\log n)^{\log \log \log n}\right)}\) (ten Cohena-Lenstry) powinien sobie jeszcze z takimi małymi liczbami jak kilkudziesięciocyfrowe poradzić dosyć sprawnie.


Nie liczyłbym za bardzo na to, że ktoś tu i teraz wymyśli lepszy test pierwszości niż wszystkie wymyślone dotychczas.

może na innych liczbach złożonych z wielu cyfr jest to dosyć trudne, ale to jest zadanie dla licealisty na poziomie 1,2 klasy. Ona na pewno nie jest tak skomplikowana, coś napewno można zrobić.

14*1+7*2+14*1+6=48
nie muszę dzielić, żeby wiedzieć że dzieli się przez 3