Cate numere prime exista?

Question

Exista vreo formula care sa arate cate numere prime exista ?

Comments

Exista o infinitate de numere prime. In momentul de fata, cel mai mare numar prim, conform wikipedia, este 2^57.885.161 - 1.

---

În ultima vreme am văzut două expuneri foarte interesante pe tema numerelor prime:

1.
2. http://www.ted.com/talks/adam_spencer_why_i_fell_in_love_with_monster_prime_numbers.html

Prima e ceva mai lungă, durează o oră, dar e plină de lucruri surprinzătoare pe care eu unul nu le știam. Nu se fac la școală și nici nu am avut nevoie de ele pe urmă. O parte se leagă și de cîte numere prime există.

Answer 1

Există teorema lui Euclid, care spune că sînt o infinitate de numere prime. Nu numai teorema e veche de peste două milenii, ci și demonstrația dată de Euclid, simplă și elegantă.

Pe scurt, dacă se ia o listă de numere prime atunci produsul lor, la care adăugăm 1, fie este el însuși un număr prim diferit de cele inițiale, fie are un factor prim care nu era în lista inițială. Ca urmare, la orice mulțime de numere prime mai putem adăuga oricînd încă unul. Deci nu terminăm niciodată.

http://en.wikipedia.org/wiki/Euclid%27s_theorem

http://mathworld.wolfram.com/EuclidsTheorems.html

Comments

si are si una din cele mai elegante demonstratii : reducerea la absurd :)

Answer 2

Un număr natural se numeşte prim dacă are exact doi divizori (1 şi el însuşi). Numarul 1 nu este nici prim nici compus, iar 2 este singurul număr şi prim şi par. Primele elemente din şirul numerelor prime sunt 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … Se cunoaşte faptul că mulţimea numerelor prime este infinită, dar nu s-a descoperit o modalitate eficientă de a determina dacă un număr foarte mare este sau nu prim. De exemplu, pentru a stabili dacă numărul 96649999 este prim sau compus, este necesar să-l împărţim pe rând la 7, 11, 13, … dar abia când ajungem la numărul 9697 constatăm că acesta este un divizor al numărului dat: 96649999 = 9697 x 9697, deci este un număr compus. Pentru a ajunge la această concluzie ar fi necesare aproape 1200 de împărţiri, ceea ce nu este uşor nici cu un calculator. Cu atât mai greu este de stabilit natura unor numere de ordinul mililiardelor sau trilioanelor, în afara unor cazuri particulare. Se ştie, de exemplu, că numerele 1111111 … 111 (23 de cifre) sau 2^4443 - 1 sunt prime, însă demonstraţiile sunt dificile. Nu se cunoaşte, de exemplu, dacă numărul 2^(2^17) + 1 (care are 39457 cifre) este prim.

O altă problemă nerezolvată de matematicieni este stabilirea numărului de numere prime mai mici decât un număr dat. Se ştie, de exemplu, că există 25 numere prime mai mici decât 100, 168 numere prime mai mici decât 1000, 1229 numere prime mai mici decât 10000, 78498 numere prime mai mici decât 1000000. Însă nu este cunoscută vreo metodă precisă de a găsi numărul de numere prime mai mici decât un număr oricât de mare, deşi mulţi matematicieni celebri s-au chinuit de-a lungul timpului să găsească o astfel de formulă.

De exemplu, matematicianul rus Cebâșev a găsit o formulă de aproximare a numărului de numere prime mai mici decât un număr oarecare n, însă eroarea formulei este semnificativă. Conform formulei lui Cebâsev, până la 1.000.000 ar fi cam 72.382 astfel de numere, ceea ce diferă cu 6.116 față de numărul adevărat (78.498). Totuși, formula lui Cebâșev reprezintă cea mai bună formulă de aproximare a numărului de numere prime mai mici decât un număr dat. O carte despre numere prime este lucrarea lui Sierpinski “Ce știm și ce nu știm despre numere prime”.