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
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 15
Wyznaczyć wszystkie pary (p,q) liczb pierwszych takich, że pq+1 i pq-1 są liczbami pierwszymi....
 szymek12  1
 liczby pierwsze - zadanie 41
wykaż, że różnica dwóch kolejnych liczb pierwszych jest zawsze mniejsza od 100 ew. podaj kontrprzykład...
 Kamilwit  4
 Liczby pierwsze - zadanie 54
A nie ma jeszcze jakiegoś założenia co do x,y,z...? Bo jeśli nie ma, to np. dla n=2 mamy 2 ^{1} \cdot 3 ^{3}=54>5 ^{2}...
 virtue  4
 liczby pierwsze - zadanie 18
-- 23 kwi 2009, o 21:34 -- p- liczba pierwsza. Wykazać, że rówanie X^{2} + Y^{2}=p ma co najmniej jedno rozwiązanie (x, y) w liczbach naturalnych takie,...
 sendzimir  1
 liczby pierwsze - zadanie 19
1.Udowodnic, ze liczb postaci 6n+1, n \ge 1 nie mozna przedstawic jako roznicy liczb pierwszych. 2.Wykazac ze miedzy liczbami n i n! (n \ge 3) znajduje sie co najmniej jedna liczba pie...
 Pumba  1
 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 51
Udowodnij, że każda liczba naturalna większa od 1 ma przynajmniej jeden dzielnik pierwszy (tj. taki, któy jest liczbą pierwszą)....
 agnieszka778  3
 Liczby pierwsze - zadanie 38
1.Niech p \in P, p>2. Pokazać, że 1^{2} \cdot 3^{2} \cdot 5^{2} \cdot\ldots\cdot (p-2)^{2} = (-1)^{ \frac{p+1}{2} } \mod p 2. Dla jakich liczb pierwszych ni...
 kasiczka15m  8
 Liczby pierwsze - zadanie 29
11(a + b + c) = abc Iloczyn liczb pierwszych abc ma 5 dzielników: 1, a, b, c, abc. Liczby a, b i...
 Kukis  4
 Liczby pierwsze - zadanie 42
Wynika stąd http://pl.wikipedia.org/wiki/Liczba_pie ... Dirichleta ...
 asqq  25
 liczby pierwsze - zadanie 22
Mam problem z następującym zadaniem: "Wyznaczyć wszystkie liczby pierwsze p, wiedzac, ze liczby p+2 , p+4 są również pierwsze. Może ktoś z Was umiałby mi pomóc?...
 KrolikWszechczasow  23
 Liczby pierwsze - zadanie 45
Wyznacz liczby pierwsze mające postać \frac{p^{2}+30}{p} , gdzie p jest liczbą pierwszą. Jak takie coś zrobić?...
 edytka96  1
 liczby pierwsze - zadanie 37
niech p będzie dowolną liczbą pierwszą udowodnij, że: \frac{1}{ p_{1} } + \frac{1}{ p_{2} } + \frac{1}{ p_{3} } + \frac{1}{ p_{n} } nie jest liczbą pierwszą....
 Elek112  1
 liczby pierwsze - zadanie 21
Wykazac ze istnieje nieskonczenie wiele liczb pierwszych postaci 4k+1, gdzie k \in \mathbb{Z}...
 Pumba  11
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com