mateforum.ro

Exista vreun algoritm care sa genereze numere prime, daca da exemplu pls...

Daca ar exista.. atunci s-ar putea genera numere prime oricat de mari... dar cum pana acum se cunosc un nr finit de numere prime... existand The largest known as zice ca nu exista nici un algoritm de acest fel.

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!

Exista ciurul lui Erathostene, exista o chestie cu studiatul resturilor impartirii la numere prime... ce fel de algoritm vrei?

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.