Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
Awatar użytkownika
rafaluk
Użytkownik
Użytkownik
Posty: 497
Rejestracja: 26 wrz 2007, o 14:41
Płeć: Mężczyzna
Lokalizacja: x=213; y=33; z=79;
Podziękował: 114 razy
Pomógł: 10 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: rafaluk » 26 wrz 2007, o 21:43

Dokładnie. Załóżmy, że chcemy to sprawdzić np. z liczbą 71. Nie wiemy, czy jest pierwsza. Więc jak to sprawdzić??
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Piotr Rutkowski
Gość Specjalny
Gość Specjalny
Posty: 2234
Rejestracja: 26 paź 2006, o 18:08
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 22 razy
Pomógł: 389 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: Piotr Rutkowski » 26 wrz 2007, o 21:49

Tutaj nie ma tak łatwo. Polecam google, gdzie można znaleźć np. to:
http://www-users.mat.uni.torun.pl/~philip/prime_t.html

marty
Użytkownik
Użytkownik
Posty: 296
Rejestracja: 4 wrz 2007, o 21:18
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 25 razy
Pomógł: 33 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: marty » 26 wrz 2007, o 21:57

jesli znasz cechy podzielnosci dasz rade
no i jesli wiesz co to jest liczba pierwsza

Awatar użytkownika
rafaluk
Użytkownik
Użytkownik
Posty: 497
Rejestracja: 26 wrz 2007, o 14:41
Płeć: Mężczyzna
Lokalizacja: x=213; y=33; z=79;
Podziękował: 114 razy
Pomógł: 10 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: rafaluk » 26 wrz 2007, o 22:09

marty pisze:jesli znasz cechy podzielnosci dasz rade
no i jesli wiesz co to jest liczba pierwsza
Znam cechy podzielności na poziomie 3 gimnazjum i bardzo dobrze wiem, czym jest liczba pierwsza, jednak za Chiny ludowe nie wiem, jak się to zadania zabrać.

marty
Użytkownik
Użytkownik
Posty: 296
Rejestracja: 4 wrz 2007, o 21:18
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 25 razy
Pomógł: 33 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: marty » 26 wrz 2007, o 22:54

dzieli sie przez 1-tak
przez 2 nie (1 -liczba jednosci)
4, 6, 8 nie bo nieparzysta jest z tylu
3, 9 tez nie bo suma cyfr daje 8 ktore z kolei nie jestpodzielne przez 3 co jest warunkiem wiec jest tol. pierwsza a co masz to udowodnic??
sprobuj rozlozyc na czynniki

Piotr Rutkowski
Gość Specjalny
Gość Specjalny
Posty: 2234
Rejestracja: 26 paź 2006, o 18:08
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 22 razy
Pomógł: 389 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: Piotr Rutkowski » 26 wrz 2007, o 22:57

Jeśli chcesz sprawdzać czy liczba jest pierwsza dla małych liczb, to najlepiej skorzystać z wymienionego już wcześniej rozkładu na czynniki (łatwo idzie dla małych liczb) lub też z sita Erastotenesa (praktycznie nadaje się tylko do 100 lub 200.

Rogal
Gość Specjalny
Gość Specjalny
Posty: 5405
Rejestracja: 11 sty 2005, o 22:21
Płeć: Mężczyzna
Lokalizacja: a z Limanowej
Podziękował: 1 raz
Pomógł: 422 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: Rogal » 27 wrz 2007, o 00:01

Oj no, zgodnie z definicją liczba jest pierwsza, jeśli nie dzieli się przez żadną mniejszą od siebie liczbę pierwszą bądź ma dokładnie dwa dzielniki - 1 i samą siebie.

Ades
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 23 wrz 2007, o 10:49
Płeć: Mężczyzna
Lokalizacja: Podkarpacie
Podziękował: 2 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: Ades » 27 wrz 2007, o 14:17

Jeżeli się nie dzieli przez żadną liczbę pierwszą równą lub mniejszą od jej połowy a dzieli się przez siebie i 1 to jest liczbą pierwszą
liczba pierwszą z wyjątkiem 2 jest liczbą nieparzystą

71 jest liczbą pierwszą

marty
Użytkownik
Użytkownik
Posty: 296
Rejestracja: 4 wrz 2007, o 21:18
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 25 razy
Pomógł: 33 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: marty » 27 wrz 2007, o 19:16

rogal, bez 0 i 1, to bardzo wazne, jest to liczba naturalna, nieparzysta, jedyna liczba parzysta ktora jest liczba pierwsza jest 2

Awatar użytkownika
rafaluk
Użytkownik
Użytkownik
Posty: 497
Rejestracja: 26 wrz 2007, o 14:41
Płeć: Mężczyzna
Lokalizacja: x=213; y=33; z=79;
Podziękował: 114 razy
Pomógł: 10 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: rafaluk » 27 wrz 2007, o 23:01

Wezcie mi tu nie piszcie, co to jest liczba pierwsza, bo to bylo w 4 klasie podstawowki, i wiem, ze 71 jest liczba pierwsza, i wiem, ze Ades zrobil blad piszac, ze 1 jest liczba pierwsza, i nie wiem nadal, jak sprawdzic, za pomoca jakich dzialan matemematycznych moglbym sprawdzic, to co chce.

Awatar użytkownika
DEXiu
Gość Specjalny
Gość Specjalny
Posty: 1174
Rejestracja: 17 lut 2005, o 17:22
Płeć: Mężczyzna
Lokalizacja: Jaworzno
Pomógł: 69 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: DEXiu » 28 wrz 2007, o 00:40

Jakich działań? Najprościej w świecie za pomocą normalnego dzielenia, bo raczej mało prawdopodobne jest, aby do poziomy szkoły średniej włącznie kazali Ci sprawdzić pierwszość liczby, która by nie przeszła tą brutalną metodą. Sprawdzasz po prostu "na pałę" czy dana liczba się dzieli po kolei przez wszystkie liczby mniejsze od siebie (prócz 1 ). Jeśli jest podzielna przez jakąkolwiek liczbę - to nie jest pierwsza. Ot cała filozofia.
P.S.Jeśli chcesz mieć nieco mniej roboty to podpowiem, że wystarczy sprawdzać podzielność danej liczby przez wszystkie liczby pierwsze mniejsze lub równe jej pierwiastkowi (w przypadku 71 - wystarczy sprawdzić podzielność przez 2, 3, 5 i 7, bo kolejna liczba pierwsza (czyli 11) jest już większa od √71 )

Rogal
Gość Specjalny
Gość Specjalny
Posty: 5405
Rejestracja: 11 sty 2005, o 22:21
Płeć: Mężczyzna
Lokalizacja: a z Limanowej
Podziękował: 1 raz
Pomógł: 422 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: Rogal » 28 wrz 2007, o 18:50

Marty, stwórz przy pomocy mej definicji jedynkę liczbą pierwszą, bo ja nie potrafię. Specjalnie ją tak wyraziłem.

Awatar użytkownika
rafaluk
Użytkownik
Użytkownik
Posty: 497
Rejestracja: 26 wrz 2007, o 14:41
Płeć: Mężczyzna
Lokalizacja: x=213; y=33; z=79;
Podziękował: 114 razy
Pomógł: 10 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: rafaluk » 29 wrz 2007, o 23:29

DEXIu, nie kaza nam nic robic. To zadanie wyszlo tak jakby przypadkowo podczas lekcji matmy, pani w koncu zaczela myslec, jakby sprawdzic (tzn. jaka najprostsza metoda) czy dana liczba jest pierwsza. Zglosilem sie, ze moge nad tym posiedziec i tak oto bza bza. A DEXIu, dzieki za podpowiedz z tym pierwiastkiem. Sam na to wpadles?

Awatar użytkownika
DEXiu
Gość Specjalny
Gość Specjalny
Posty: 1174
Rejestracja: 17 lut 2005, o 17:22
Płeć: Mężczyzna
Lokalizacja: Jaworzno
Pomógł: 69 razy

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Post autor: DEXiu » 30 wrz 2007, o 01:02

rafaluk ==> W sumie to już nie wiem czy sam czy nie sam (raczej gdzieś usłyszałem ). To dość prosty wniosek. Bo przecież jeśli zapiszemy jakąś liczbę jako iloczyn dwóch liczb od niej mniejszych (przy czym te dwie liczby nie muszą być pierwsze, ale mogą; natomiast gdyby nasza liczba była pierwsza to oczywiście nie uda nam się jej tak zapisać, ale to właśnie chcemy sprawdzić powyższą metodą), to logiczne jest, że każdy taki zapis będzie się składał z dwóch czynników, z których jeden jest niewiększy, a drugi niemniejszy od pierwiastka z tej liczby (iloczyn pierwiastka z tej liczby przez samego siebie da nam tą liczbę, a jeśli będziemy jeden czynnik chcieli zmniejszyć, to drugi automatycznie będzie rósł, tak aby ich iloczyn cały czas był stały i był równy naszej liczbie - to chyba oczywiste).
Wniosek z tego jest taki, że jeśli jakaś liczba nie posiada żadnego dzielnika (różnego od 1 i siebie samej) mniejszego lub równego jej pierwiastkowi, to nie posiada go wcale (gdyby posiadała dzielnik większy od jej pierwiastka, to taki dzielnik musiałby mieć swoją "parę" "po drugiej stronie" pierwiastka, a przecież sprawdziliśmy, że takowych nie ma)

Heh. Było powiedzieć nauczycielce żeby sprawdziła w tablicach matematycznych Najprościej i najszybciej w przypadku sporych liczb, co do których nie mamy pewności

ODPOWIEDZ