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

rafaluk · 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ć??

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

Tutaj nie ma tak łatwo. Polecam google, gdzie można znaleźć np. to:

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

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

rafaluk · 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 · 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 · 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 · 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 · 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 · 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

rafaluk · 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.

DEXiu · 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 · 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.

rafaluk · 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?

DEXiu · 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