Liczba pierwsza?

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
brzuszek04
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 22 lis 2008, o 11:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1 raz

Liczba pierwsza?

Post autor: brzuszek04 »

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
Awatar użytkownika
kuch2r
Użytkownik
Użytkownik
Posty: 2302
Rejestracja: 18 paź 2004, o 18:27
Płeć: Mężczyzna
Lokalizacja: Wrocław/Ruda Śląska
Podziękował: 9 razy
Pomógł: 408 razy

Liczba pierwsza?

Post autor: kuch2r »

... zo%C5%9Bci
zajrzyj tutaj
brzuszek04
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 22 lis 2008, o 11:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1 raz

Liczba pierwsza?

Post autor: brzuszek04 »

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...
Awatar użytkownika
Gacuteek
Użytkownik
Użytkownik
Posty: 1075
Rejestracja: 13 mar 2008, o 21:54
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 5 razy
Pomógł: 272 razy

Liczba pierwsza?

Post autor: Gacuteek »

hmm. może skorzystaj z tego że liczba "p" jest pierwsza gdy zachodzi :
\(\displaystyle{ p|(p-1)!+1}\)
brzuszek04
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 22 lis 2008, o 11:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1 raz

Liczba pierwsza?

Post autor: brzuszek04 »

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
frej

Liczba pierwsza?

Post autor: frej »

Podzielne przez \(\displaystyle{ 3}\)
Awatar użytkownika
max
Użytkownik
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?

Post autor: max »

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.
brzuszek04
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 22 lis 2008, o 11:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1 raz

Liczba pierwsza?

Post autor: brzuszek04 »

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.
Xitami

Liczba pierwsza?

Post autor: Xitami »

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

Liczba pierwsza?

Post autor: frej »

ODPOWIEDZ