Test de primalitate cu ciur

Să recapitulăm: verificăm dacă un număr N este prim efectuând proba împărțirii. Aici este rădăcina pătrată a lui N iar aici este numărul trei. Începând de la 3, sărim cu câte doi până la rădăcina pătrată a lui N. La fiecare pas de pe parcurs, verificăm dacă acel număr îl divide pe N. Până acum, oamenii au încercat să reducă numărul de pași începând de mai încolo și făcând pași mai mari. Aș vrea să facem o pauză și să ne gândim: Care este cazul ideal pentru un algoritm cu proba împărțirii? Care e cel mai bun lucru pe care îl putem face dacă devenim foarte creativi pe parcursul nostru? Amintește-ți, orice număr N are o descompunere în factori primi. Să presupunem că rădăcina pătrată a lui N este aici. Avem nevoie să parcurgem doar numerele prime. Acesta ar fi cel mai bun lucru pe care le-am putea face. Știm că dacă trecem doar prin numerele prime, vom găsi până la urmă un factor. Un factor prim dacă numărul este compus. Acum ne întrebăm: cât de eficientă este această metodă? Pare că avem o soluție perfectă acum. Dacă am fi scris un nou algoritm care să apeleze mai întâi ciurul? Să zicem că noul algoritm verifică dacă N este număr prim. Dacă mai întâi apelăm ciurul și generăm o listă cu numerele prime până la radical din N, apoi verificăm prin împărțire, folosind această listă de numere prime? Am trece doar prin numere prime până la rădăcina pătrată a lui N, oriunde ar fi aceasta. Ce e în neregulă cu această abordare? Putem vizualiza complexitatea din punct de vedere al timpului, sau numărul de pași care se execută. Amintește-ți că am făcut asta- Am aplicat acest algoritm și am folosit un contor de pași în fiecare buclă; avem- să zicem că Step++ înseamnă că numărul de pași crește cu unu. În interiorul acestei bucle avem și aici un contor de pași. Step++ Acestea sunt operații constante de verificare și marcare. Deci avem un contor de pași în interiorul fiecărei bucle. Aici avem o comparație. În stânga este metoda veche de probă a împărțirii. În mijloc este algoritmul nostru care apelează ciurul pentru a genera toate numerele prime până la N. În dreapta avem varianta în care apelăm ciurul pentru a genera numere prime până la rădăcina pătrată a lui N și apoi apelăm testul de primalitate doar cu aceste numere prime. Să vedem ce se întâmplă cu un număr mic. După cum vedem, inițial, ciurul face mulți pași. Până și varianta modificată în dreapta este de fapt mai lentă decât proba împărțirii. Cu cât numărul de testat crește, cu atât numărul de pași din ciur crește și el. Să uităm de mijloc și să comparăm proba împărțirii versus ciurul până la rădăcina pătrată a lui N urmat de proba împărțirii. Vedem aici că vechea metodă de probă a împărțirii este mult mai eficientă. Numărul de pași din ciur, până la rădăcina pătrată a lui N urmat de proba împărțirii crește mult mai repede. De fapt, nu este o îmbunătățire. Acesta este programul pe care l-am folosit pentru comparație. Avem și o înregistrare cu explicații. Acum te-ai putea întreba: "Ce ar fi dacă am calcula numerele prime în avans?" Primul pas ar fi să construim o listă de numere prime și să o stocăm pe hard disk. Apoi, algoritmul nostru ar face doar proba împărțirii și ar ști să treacă doar prin numerele prime deoarece ar citi din această listă propusă de numere prime. Poate că în listă se stochează toate numerele prime până la 20 de cifre sau chiar până la 100 de cifre. De ce nu putem face asta? Problema este cu limitările memoriei, când enumerăm liste de numere, lucru pe care îl vom descoperi în continuare. Să zicem, ipotetic, că am face acest lucru de mână. Vedem că 5 este prim, scriem cinci pe o bucată de hârtie, și o stocăm într-un dulăpior de dosare. Apoi obținem șapte, depozităm și asta în dulăpior. Apoi 9, 11, în dulăpior. La final avem un dulap plin de numere prime. Gândește-te că aceasta ar fi lista noastră de numere prime. Cât de mare ar fi acest dulap dacă, să zicem, am vrea toate numerele prime de până la 20 de cifre sau de până la 100 de cifre? Am putea păstra o așa listă pe un mediu de stocare nevolatilă? Ca să înțelegem de ce nu e posibil acest lucru, trebuie să explorăm mai în amănunt cât de mare poate să devină această listă de numere prime și care sunt limitările de spațiu ale calculatoarelor moderne sau chiar din viitor.