szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
 Tytuł: liczby pierwsze
PostNapisane: 29 lip 2004, o 13:31 
Użytkownik
Kto mi przedstawi najszybszy algorytm na sprawdzenie czy liczba x jest liczba pierwsza. :D
Góra
Instytut Matematyczny, Uniwersytet Wrocławski
Mężczyzna Offline
 Tytuł: liczby pierwsze
PostNapisane: 29 lip 2004, o 14:18 
Gość Specjalny

Posty: 534
Lokalizacja: Warszawa
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.
Góra
Mężczyzna Offline
 Tytuł: liczby pierwsze
PostNapisane: 29 lip 2004, o 15:06 
Gość Specjalny
Avatar użytkownika

Posty: 1179
Lokalizacja: krk
Reksio napisał(a):
Na poczatku sprawdz czy liczba jest parzysta...


i przy tym rozna od 2 :]
Góra
Mężczyzna Offline
 Tytuł: liczby pierwsze
PostNapisane: 29 lip 2004, o 21:54 
Gość Specjalny

Posty: 534
Lokalizacja: Warszawa
Tak tak trzeba sprawdzic, ale to byl tylko taki "szkic":)
Góra
Offline
 Tytuł: liczby pierwsze
PostNapisane: 30 lip 2004, o 07:52 
Gość Specjalny
Avatar użytkownika

Posty: 54
Lokalizacja: Poznań
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...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczby pierwsze - zadanie 2
Czy dla dowolnej liczby całkowitej p>1, liczba p jest pierwsza wtedy i tylko wtedy, gdy: a) p nie dzieli się przez żadną liczbę całkowitą k taką, że 1...
 alexandra  1
 Liczby pierwsze - zadanie 3
Zamieszczam tutaj link do ściągnięcia programiku mojego autorstwa dotyczącego liczzb pierwszych. Może komuś kiedyś się przyda. http://rapidshare.de/files/26016930/Project2.exe.html Po odpaleniu linka na...
 DS88  12
 Liczby pierwsze - zadanie 4
jak oszacować ilość liczb pierwszych mniejszych od 1000? jest jakiś algorytm lub wzór na takie szacowanie?...
 Esiak  8
 Liczby pierwsze - zadanie 6
Dla liczby całkowitej p>1, liczba p jest pierwsza wtedy i tylko wtedy, gdy p nie dzieli się przez żadną liczbę całkowitą k taką, że 1...
 pokemmon_21  1
 Liczby pierwsze - zadanie 7
Znajdź wszystkie trójki liczb pierwszych p, q, r takie, że: p^q+q^p=r...
 wb  2
 liczby pierwsze - zadanie 8
Proszę o wskazówki do zadań poniższych. Nie mam na nie pomyslu!!!! 1. Znajdź taką liczbe naturalną n, że zbiór {n, n+1, n+2, n+3, n+4, n+5} zawiera najwięcej liczb pierwszych. 2. Czy liczby p, p+6, p+18, p+24, p+30 mogą być jednocześnie liczbami pier...
 beata1964  4
 Liczby pierwsze - zadanie 9
1. Wykaż, że jeżeli liczby p i 5p^2-2 są pierwsze, to liczby 5p^2-4 i 5p^2+2 też są pierwsze 2. Wykaż, że jeżeli liczby p i 2p^2+13 są...
 matshadow  3
 liczby pierwsze - zadanie 10
Witam i prosze o pomoc w takim zadaniu: 1. Wyznacz wszystkie liczby całkowite dodatnie n, dla których liczba 14 ^{n} - 9 jest pierwsza. dziękuje za pomoc!!!!...
 beata1964  1
 Liczby pierwsze - zadanie 11
Pięciokrotna suma liczb pierwszych p, q, r równa jest iloczynowi tych liczb. Wyznaczyć te liczby. Samemu doszedłem do tego, że jedna musi być równa 5, a potem tak bardziej 'na oko' i podstawiając do równania funkcji wymiernej, że pozostałe to 2 i ...
 Noegrus  7
 Liczby pierwsze - zadanie 12
Dane są liczby pierwsze p i q. Liczba p dzieli liczbę q ^{3}-1, zaś liczba q dzieli liczbę ...
 szymek12  2
 Liczby pierwsze - zadanie 13
Witam, mam problem z następującym zadaniem: Pokazać, że jeśli p jest liczbą pierwszą większą od 5, to p^{2} przy dzieleniu przez 30 daje reszte równą 1 lub 19. Dziękuje za wszelką pomoc....
 Adrian1234  3
 Liczby pierwsze - zadanie 14
Wykazać, że dla każdej naturalnej n>2 liczby a=2 ^{n}+1, b=2 ^{n}-1 nie mogą być jednocześnie liczbami pierwszymi....
 szymek12  6
 liczby pierwsze - zadanie 15
Wyznaczyć wszystkie pary (p,q) liczb pierwszych takich, że pq+1 i pq-1 są liczbami pierwszymi....
 szymek12  1
 Liczby pierwsze - zadanie 16
Witam Mam problem z takim zadankiem. Czy mógłby ktoś je zrobić i krok po kroku wyjaśnić. Dla jakich liczb pierwszych m i [tex:3822b29...
 lukki_173  3
 liczby pierwsze - zadanie 17
Ciąg (a_n) okreslony jest wzorem a_n=4n-13. Znajdz wszystkie liczby naturalne k takie, ze wyrazy a_k, a_{k+1}, a_{k+2} są liczbami pierwszymi....
 porbaj  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com