Exista un algoritm care sa genereze numere prime?
Moderator: Filip Chindea
-
Baiatul destept
- Euclid
- Posts: 13
- Joined: Fri Oct 12, 2007 7:17 am
Exista un algoritm care sa genereze numere prime?
Exista vreun algoritm care sa genereze numere prime, daca da exemplu pls...
Un nebun pescuia intr-o cada.Un medic, cu o metoda proprie, il intreaba daca a prins ceva. Nebunul ii raspunde sever:"Bineinteles ca nu, prostule, nu vezi ca e o cada!"
-
Baiatul destept
- Euclid
- Posts: 13
- Joined: Fri Oct 12, 2007 7:17 am
????
Raspunsul nu putea fi decat da sau nu!, orikum explicatia ta este cel putin dubioasa!!
Intreb lucrul acesta pentru ca am gasit o particularitate interesanta:
Pentru cateva triplete (p1, p2, p3) 3 nr. prime; p1p2+p2p3+p1p3 este tot numar prim ceea ce mi se pare destuld e interesant in sens ca desi kestia asta se aplica pentru un nr destul de mic de numere prime, poate fi varful de aisberg care sa evidentieze eventual un algoritm de generare....sau poate nu!
Intreb lucrul acesta pentru ca am gasit o particularitate interesanta:
Pentru cateva triplete (p1, p2, p3) 3 nr. prime; p1p2+p2p3+p1p3 este tot numar prim ceea ce mi se pare destuld e interesant in sens ca desi kestia asta se aplica pentru un nr destul de mic de numere prime, poate fi varful de aisberg care sa evidentieze eventual un algoritm de generare....sau poate nu!
Un nebun pescuia intr-o cada.Un medic, cu o metoda proprie, il intreaba daca a prins ceva. Nebunul ii raspunde sever:"Bineinteles ca nu, prostule, nu vezi ca e o cada!"
-
Dumitran_Marius
- Posts: 2
- Joined: Mon Dec 03, 2007 12:18 am
Exista ciurul lui Eratostene, gasesti multe despre el pe net. Are complexitate O(n loglogn), deci aproape O(n) poti genera lejer pana in 10 milioane in 2-3 secunde... si cu rabdare in cateva minute toate sub 1 miliard...
Exita si un algoritm in O(n), dar sincer nu il stiu. Mi-a picat o data in mana, mi s-a blocat compul cand am deschis pdf-ul si nu am mai dat de el, dar banuiesc ca constanta mare l-ar face sa mearga comparabil cu ciurul pentru valori mici.
Pentru numere mai mari ca 10^9 metode uzual folosite sunt generarea numerelor random si apoi testarea primalitatii lor prin diverse metode.
Ai putea citi mai multe aici
http://en.wikipedia.org/wiki/Primality_test
Oricum se folosesc mai ales testele Rabin si Solovay-Strassen primality test
care nu sunt nici prea greu de implementat.
Ideea de baza e ca numele prime sunt dese: n/log(n) sunt prime -> daca alegi random de 100 de cifre... daca alegi vreo 300 de numere deja sansele sa alegi unu prim e bun.
Cum complexitatea de testare cu alg probabilistiti e log(n) -> gasesti numere prime repede.
Exita si un algoritm in O(n), dar sincer nu il stiu. Mi-a picat o data in mana, mi s-a blocat compul cand am deschis pdf-ul si nu am mai dat de el, dar banuiesc ca constanta mare l-ar face sa mearga comparabil cu ciurul pentru valori mici.
Pentru numere mai mari ca 10^9 metode uzual folosite sunt generarea numerelor random si apoi testarea primalitatii lor prin diverse metode.
Ai putea citi mai multe aici
http://en.wikipedia.org/wiki/Primality_test
Oricum se folosesc mai ales testele Rabin si Solovay-Strassen primality test
care nu sunt nici prea greu de implementat.
Ideea de baza e ca numele prime sunt dese: n/log(n) sunt prime -> daca alegi random de 100 de cifre... daca alegi vreo 300 de numere deja sansele sa alegi unu prim e bun.
Cum complexitatea de testare cu alg probabilistiti e log(n) -> gasesti numere prime repede.