Număr prim | număr natural de un anumit tip

Există o metodă simplă pentru a găsi o listă de numere prime. Eratostene a creat-o. Ea poartă numele de "Sita lui Eratostene". Aceasta prinde numerele care nu sunt prime (ca o sită) și lasă să treacă numerele prime.

Metoda funcționează cu o listă de numere și cu un număr special numit b, care se modifică în timpul metodei. Pe măsură ce cineva parcurge metoda, încercuiește unele numere din listă și le taie pe altele. Fiecare număr încercuit este prim, iar fiecare număr tăiat este compus. La început, toate numerele sunt simple: nu sunt încercuite și nu sunt tăiate.

Metoda este întotdeauna aceeași:

1. Pe o foaie de hârtie, scrieți toate numerele întregi de la 2 până la numărul testat. Nu scrieți numărul 1. Treceți la pasul următor.
2. Începeți cu b egal cu 2. Treceți la pasul următor.
3. Încercuiți b în listă. Treceți la pasul următor.
4. Pornind de la b, numărați încă b în listă și tăiați numărul respectiv. Repetați numărarea a încă b numere în sus și tăierea numerelor până la sfârșitul listei. Treceți la pasul următor.
• (De exemplu: Când b este 2, veți încercui 2 și veți tăia 4, 6, 8, și așa mai departe. Când b este 3, veți încercui 3 și veți tăia 6, 9, 12 și așa mai departe. 6 și 12 au fost deja tăiate. Tăiați-le din nou).
5. Creșteți b cu 1. Treceți la pasul următor.
6. Dacă b a fost tăiat, reveniți la etapa anterioară. Dacă b este un număr din listă care nu a fost tăiat, treceți la a treia etapă. Dacă b nu se află în listă, treceți la ultima etapă.
7. (Acesta este ultimul pas.) Ați terminat. Toate numerele prime sunt încercuite și toate numerele compuse sunt tăiate cu o cruce.

De exemplu, se poate aplica această metodă la o listă de numere de la 2 la 10. La final, numerele 2, 3, 5 și 7 vor fi încercuite. Acestea sunt numere prime. Numerele 4, 6, 8, 9 și 10 vor fi tăiate. Acestea sunt numere compuse.

Această metodă sau algoritm durează prea mult timp pentru a găsi numere prime foarte mari. Cu toate acestea, este mai puțin complicată decât metodele utilizate pentru numere prime foarte mari, cum ar fi testul de primalitate al lui Fermat (un test pentru a vedea dacă un număr este prim sau nu) și testul de primalitate Miller-Rabin.

Numerele prime sunt foarte importante în matematică și informatică. Numerele foarte lungi sunt greu de rezolvat. Este dificil de găsit factorii lor primi, astfel încât, de cele mai multe ori, numerele care sunt probabil prime sunt folosite pentru criptare și coduri secrete. De exemplu:

• Cei mai mulți oameni au un card bancar, de pe care pot scoate bani din contul lor folosind un bancomat. Acest card este protejat de un cod de acces secret. Deoarece codul trebuie să fie păstrat secret, acesta nu poate fi stocat în clar pe card. Criptarea este utilizată pentru a stoca codul în mod secret. Această criptare utilizează înmulțiri, diviziuni și găsirea resturilor numerelor prime mari. În practică, se folosește adesea un algoritm numit RSA. Acesta utilizează teorema restului chinezesc.

• În cazul în care cineva are o semnătură digitală pentru e-mailul său, se utilizează criptarea. Astfel, se asigură că nimeni nu poate falsifica un e-mail de la această persoană. Înainte de a semna, se creează o valoare hash a mesajului. Aceasta este apoi combinată cu o semnătură digitală pentru a produce un mesaj semnat. Metodele utilizate sunt mai mult sau mai puțin aceleași ca în primul caz de mai sus.

• Găsirea celui mai mare număr prim cunoscut a devenit, de-a lungul anilor, un fel de sport. A testa dacă un număr este prim poate fi dificil dacă numărul este mare. Cele mai mari numere prime cunoscute la un moment dat sunt, de obicei, numerele prime Mersenne, deoarece cel mai rapid test cunoscut pentru primalitate este testul Lucas-Lehmer, care se bazează pe forma specială a numerelor Mersenne.

• Coprime
• Lista numerelor prime
• Prim palindromic
• Factorizarea primelor
• Wilson prime