liczby pierwsze
liczby pierwsze
Kto mi przedstawi najszybszy algorytm na sprawdzenie czy liczba x jest liczba pierwsza.
-
- Gość Specjalny
- Posty: 534
- Rejestracja: 8 lip 2004, o 17:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 17 razy
liczby pierwsze
zrob funkcje ktora bdzie zwracac true jesli pierwsza false jesli nie. Zaloz najpierw ze liczba jest pierwsza. Na poczatku sprawdz czy liczba jest parzysta, pozniej sprawdzaj czy kolejne liczby nieparzyste wieksze 1, nie wieksze od pierwiastka kwadratowego tej liczby nie sa jej dzielnikami. Na koniec kaz skonczyc odliczanie jesli bedzie wiadomo, ze liczba jest zlozona, niby taki maly szczegol, ale przyspiesza.
-
- Użytkownik
- Posty: 1179
- Rejestracja: 21 cze 2004, o 00:51
- Płeć: Mężczyzna
- Lokalizacja: krk
- Pomógł: 9 razy
liczby pierwsze
i przy tym rozna od 2 :]Reksio pisze: Na poczatku sprawdz czy liczba jest parzysta...
liczby pierwsze
mozna tez wykozystac tzw. algorytm na test pierwszosci liczb wykonujc nastepujace kroki...
1. sprawdzamy czy a jest liczba pierwsza.
2. obliczamy c=(b^(a-1)) mod a. tak ze b nie jest wielokrotnoscia liczby a.
(dla ulatwienia wiemy ze 2 jest liczba pierwsza...a w dalszych obliczeniach bierzmy b=2, po to aby nie dostawac duzych liczb, ktore na pewno beda potrzebne, ale jest to na pewno szbki algorytm)
3. jesli c=1 => a jest liczba pierwsza. w przeciwnym wypadku a jest liczba zlozona...
napisalem kiedys taki programik we free pascalu.napisalem go aby sprawdzac czy liczby postaci (3^n)-1 sa liczbami pierwszymi...i tak doszedlem do wyniku gdzies okolo n=4000...i to dzialalo na prawde szybko jak na takie liczby... o testach pierwszosci liczb duzo jest napisane w ksiazce Donalda Knutha poszukajcie... a takze cos powinno byc w teorii liczb sierpinskiego...
1. sprawdzamy czy a jest liczba pierwsza.
2. obliczamy c=(b^(a-1)) mod a. tak ze b nie jest wielokrotnoscia liczby a.
(dla ulatwienia wiemy ze 2 jest liczba pierwsza...a w dalszych obliczeniach bierzmy b=2, po to aby nie dostawac duzych liczb, ktore na pewno beda potrzebne, ale jest to na pewno szbki algorytm)
3. jesli c=1 => a jest liczba pierwsza. w przeciwnym wypadku a jest liczba zlozona...
napisalem kiedys taki programik we free pascalu.napisalem go aby sprawdzac czy liczby postaci (3^n)-1 sa liczbami pierwszymi...i tak doszedlem do wyniku gdzies okolo n=4000...i to dzialalo na prawde szybko jak na takie liczby... o testach pierwszosci liczb duzo jest napisane w ksiazce Donalda Knutha poszukajcie... a takze cos powinno byc w teorii liczb sierpinskiego...