pisanie programu w pascalu

Rutek · Post autor: **Rutek** » 21 lis 2005, o 16:37

Musze napisac program w pascalu o takeij tresci : Napisz program , ktory będzie sprawdzał czy podana z klawiatury liczba jest liczbą pierwszą??Prosze o pomoc!

Sulik · Post autor: **Sulik** » 21 lis 2005, o 17:00

Liczba n jest pierwsza jeśli nie ma dzilników innych niż 1 i n oraz jest większa od 1. Czy liczba jest dzielnikiem sprawdzasz licząc resztę z dzielenia - tj. jeśli n mod k = 0 to znaczy, że k jest dzielnikiem n. Trzeba sprawdzić dla wszystkich k od 2 to n-1.

Tomasz Rużycki · Post autor: **Tomasz Rużycki** » 21 lis 2005, o 19:11

Wystarczy sprawdzać dzielniki do części całkowitej pierwiastka z \(\displaystyle{ n}\).

Pozdrawiam,
--
Tomek Rużycki

juzef · Post autor: **juzef** » 21 lis 2005, o 20:00

Proponuję użyć algorytmu AKS.

Fibik · Post autor: **Fibik** » 24 lis 2005, o 20:50

Może ktoś oszacować ile jest liczb pierwszych mniejszych od 2^32 oraz 2^64.

juzef · Post autor: **juzef** » 24 lis 2005, o 23:52

\(\displaystyle{ 2^{32}}\) - 203280221
\(\displaystyle{ 2^{64}}\) - trochę więcej niż \(\displaystyle{ 4,2\cdot 10^{17}}\)

Fibik · Post autor: **Fibik** » 25 lis 2005, o 00:06

Jakoś strasznie dużo, liczyłeś to tak:
\(\displaystyle{ \large N(n) \mathrm{Li}(n) = \int_{2}^{n}\frac{\mathrm{d}t}{\ln |t|}}\)

juzef · Post autor: **juzef** » 25 lis 2005, o 16:03

Pierwsza wartość jest dokładna. Ta druga to efekt zastosowania LogIntegral[2^64] w Mathematice. \(\displaystyle{ \frac{2^{64}}{ln(2^{64})-1}}\) daje podobny wynik.

edit Dokładna wartość to 425656284035217743

meFisto · Post autor: **meFisto** » 28 gru 2005, o 15:34

czym jest algorytm aks?

juzef · Post autor: **juzef** » 28 gru 2005, o 16:34

Niedawno wymyślony algorytm do sprawdzania czy liczba jest pierwsza. Ciekawa rzecz z matematycznego punktu widzenia. Niestety zupełnie nieprzydatny w praktyce.

Gobol · Post autor: **Gobol** » 28 gru 2005, o 17:19

możesz coś wiecej napisać o tym algorytmie?