Liczba pierwsza?
-
- Użytkownik
- Posty: 10
- Rejestracja: 22 lis 2008, o 11:08
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Liczba pierwsza?
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
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
-
- Użytkownik
- Posty: 10
- Rejestracja: 22 lis 2008, o 11:08
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Liczba pierwsza?
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...
-
- Użytkownik
- Posty: 10
- Rejestracja: 22 lis 2008, o 11:08
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Liczba pierwsza?
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
(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
- max
- Użytkownik
- Posty: 3306
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
Liczba pierwsza?
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.
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.
-
- Użytkownik
- Posty: 10
- Rejestracja: 22 lis 2008, o 11:08
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Liczba pierwsza?
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ć.
Ostatnio zmieniony 22 gru 2008, o 17:53 przez brzuszek04, łącznie zmieniany 1 raz.