Conţinutul principal
Curs: Mate pentru Info > Unitatea 10
Lecția 3: Numere prime- Numere prime
- Recunoașterea numerelor prime și a celor compuse
- Găsește numere prime
- Găsește numere compuse
- Numere prime și numere compuse
- Provocarea test de primalitate
- Algoritmul de încercarea prin împărțire
- Ciurul lui Eratostene
- Test de primalitate cu ciur
© 2024 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie
Ciurul lui Eratostene
Ciurul lui Eratostene ne permite să generăm o listă de numere prime. Creat de Brit Cruise.
Vrei să te alături conversației?
Nici o postare încă.
Transcript video
Acum îți voi prezenta
o metodă antică pentru a genera o listă de numere prime până la o limită N, metodă numită
Ciurul lui Eratostene. Eratostene s-a născut în 276 î.e.n. Deci, această metodă e veche
de 2200 de ani. Dar este foarte simplă și elegantă și o poți prezenta oricărui copil. Să zicem că vrem să calculăm toate numerele prime până la 100, S-ar proceda exact la fel
dacă am vrea să calculăm până la 10 000 sau un miliard. Uite cum facem:
presupunem că toate numerele sunt nemarcate
(gri înseamnă nemarcat). Începem de la doi:
dacă găsim un număr care e nemarcat, vom ști că e prim. Îl avem pe doi: doi este prim
deoarece nu e marcat. În a doua etapă eliminăm toți multiplii lui doi: știm că reprezintă
numere compuse. Bum, parcurgem numerele și eliminăm toți multiplii lui doi;
roșu înseamnă compus. Iar acum repetăm. Trecem de la doi la trei. Trei este nemarcat așa că vom
marca trei ca fiind prim. Iar acum putem elimina
toți multiplii lui trei. Putem să facem mai rapid: - observă că șase este deja tăiat - vom marca de fapt
toți multiplii începând de la pătratul perfect al acelui număr. Așadar trei înmulțit cu trei este nouă. Începem de la nouă și marcăm toți multiplii lui trei ca fiind compuși. Iar apoi ne întoarcem
și sărim la patru. Patru e deja marcat,
știm că este prim. Trecem la cinci, și găsim un
alt număr nemarcat, cinci, care este prim. Acum, de cinci ori cinci dă 25,
vom sări la 25. Marcăm 25, 30, 35, 40, 45, și așa
mai departe. Acestea sunt numere compuse. Mergem înainte până ajungem la șapte, știm că șapte este prim
deoarece nu este marcat. Șapte înmulțit cu șapte este 49,
marcăm 49 iar apoi marcăm toți multiplii lui 7
de după 49 ca fiind compuși. Revenim și ajungem la 11,
11 este prim. Observă că 11 înmulțit cu 11
dă un număr mai mare decât 100, deci ne putem opri în acest punct. Ne-am fi putut opri la 10 chiar, deoarece acum toate numerele
rămase nemarcate, după cum se vede, sunt prime. Iar, cu o singură mișcare, le
marcăm pe toate ca fiind prime. Iar acesta e întregul algoritm,
e atât de simplu. Acum, să generalizăm
ce am făcut, pentru a scrie un program care
să treacă numerele prin ciur. Dacă vrem să găsim
toate numerele prime până la un număr N, trebuie
întâi să creăm o buclă principală. Deci avem pentru toate numerele A, de la 2 până la rădăcina pătrată a lui N. Remarcă, aici ne-am oprit
când am ajuns la 10. Am arătat la 11, ne oprim fiindcă am găsit toate numerele prime. Deci de la 2 până la
rădăcina pătrată a lui N, procedăm așa: dacă A e nemarcat, atunci știm că A e prim,
iar când găsim un număr prim marcăm toți multiplii lui A ca fiind numere compuse. Asta e tot! Deci, găsești un număr prim,
îi marchezi multiplii, te întorci la început,
incrementezi A cu unu. Deci suntem la doi și trecem la trei apoi la patru, cinci și așa mai departe, iar când terminăm, am aflat toate
numerele prime. Vezi aici că și aceasta este o buclă. Avem o buclă principală pentru
când găsim un număr prim. Iar această marcare a multiplilor
e și ea la rândul ei o buclă. E important de văzut aici că avem o buclă imbricată, avem o buclă în interiorul alteia. Aici e un exemplu în acțiune
al acestui algoritm, l-am scris aici în JavaScript. Dacă pun 100, vedem aici
toate numerele prime sub 100. Dacă pun 200, avem aici
toate numerele prime sub 200. Iar dacă pun 850, vedem aici
toate numerele prime sub 850. Astfel avem acest program
cu o înregistrare care explică cum l-am creat.