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 » 21 gru 2008, o 17:26

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
Gość Specjalny
Gość Specjalny
Posty: 2303
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 » 21 gru 2008, o 18:14

http://pl.wikipedia.org/wiki/Kategoria: ... 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 » 21 gru 2008, o 22:21

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
Gość Specjalny
Gość Specjalny
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 » 21 gru 2008, o 23:05

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 » 22 gru 2008, o 12:23

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 » 22 gru 2008, o 12:32

Podzielne przez \(\displaystyle{ 3}\)

Awatar użytkownika
max
Gość Specjalny
Gość Specjalny
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 » 22 gru 2008, o 12:37

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 » 22 gru 2008, o 12:42

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 » 22 gru 2008, o 13:00

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

frej

Liczba pierwsza?

Post autor: frej » 22 gru 2008, o 13:20


ODPOWIEDZ