Algoritmul de încercarea prin împărțire

Definirea problemei

Trebuie să construim o mașinărie care poate să răspundă la o intrebare simplă cu da/nu. Fiind dat un număr întreg n, este n prim?

Hai să ne gândim cum ar putea funcționa această mașinărie. Mașinăriile pot doar să execute o secvență de pași dată prin instrucțiuni, secvență care se numește algoritm. Pentru început, să încercăm să scoatem la lumină algoritmul din mintea noastră. Răspunde la întrebarea: 49 este număr prim?

…

Nu? Cum ai aflat? Probabil că ai căutat un divizor al lui 49 care să fie mai mare decât 1 și mai mic decât 49. Dacă nu ai învățăt tabla înmulțirii, atunci ți se pare natural să parcurgi următoarea secvență:

2 este divizor al lui 49? NU
3 este divizor al lui 49? NU
4 este divizor al lui 49? NU
5 este divizor al lui 49? NU
6 este divizor al lui 49? NU
7 este divizor al lui 49? DA

Am găsit un divizor al lui 49 (7) care ne demonstrează că 49 este număr compus.

Fixarea unui prag

Dar dacă ți-aș spune să verifici dacă 2971215073 este sau nu număr prim?

Încă mai verifici? După primele câteva mii de încercări, eu nu am găsit un divizor. Întrebarea cheie este: când ne putem opri și spune că n este număr prim? (hai să îi spunem prag) La început, știam că pragul nostru trebuie să fie n-1 (deoarece n este divizor al lui n). Dacămergem cu verificările până la 2971215072 fie găsim un divizor (care ar demonstra că n este număr compus) FIE nu găsim (ceea ce înseamnă că n este număr prim).

Fixarea unui prag mai bun

Ar funcționa, dar am putea să micșorăm pragul pentru a economisi timp? Amintește-ți, noi de fapt căutăm orimul (cel mai mic) divizor. Uneori, acest cel mai mic divizor este 2, dar alteori ar putea să fie un număr mult mai mare. Ajungem astfel la următoarea întrebare cheie: cât de mare poate fi cel mai mic divizor?

Să ne reamintim că orice număr întreg compus n este format cu două sau mai multe numere prime n= P * P …

P este maxim când n are exact doi divizori care sunt egali între ei. Un astfel de număr se numește pătrat perfect, de exemplu 9 (9 = 33) sau 49 (49 = 77). Pentru a trata și acest cel mai nefavorabil caz, pur și simplu stabilim pragul la radical (rădăcina pătrată) din n.

Convinge-te de asta: dacă nu găsim un divizor al lui n până la radical din n, atunci n cu siguranță este număr prim. Încearcă să îți demonstrezi asta (găsești o demonstrație la sfârșitul acestui articol)

Algoritm de încercare prin împărțire

Asta-i tot! Acum putem merge mai departe. Mai întâi, să rezumăm algoritmul de încercare prin împărțire, scriindu-l în limbaj natural:

Se dă ca dată de intrare un număr întreg n
Pentru fiecare număr întreg x de la {2 ... radical(n)} verificăm dacă x este divizor al lui n
Dacă găsim un divizor, atunci n este număr compus SAU ALTFEL n este număr prim

Dacă ai experiență în programare, poți crea o ciornă de program și încearcă să implementezi o funcție pentru asta. Dacă nu, poți trece la pasul următor, unde găsești o versiune funcțională pe care am creat-o deja pentru tine ca punct de pornire. (Notă: Este posibil să parcurgi lecția aceasta fără să faci partea de programare).

Vrei să te alături conversației?

Conectare

Ordonare după:

Nici o postare încă.

Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.