Jumătate din subiectele de BAC încep cu „se citește un număr natural n…". Azi înveți uneltele care rezolvă toată familia: extragerea cifrelor, divizorii și algoritmul lui Euclid — vechi de 2300 de ani, încă neînvins.
Patru formule care apar în 90% din problemele cu numere. Învață-le ca pe tabla înmulțirii.
restul împărțirii la 10 · 573 % 10 = 3
573 / 10 = 57 — împărțire întreagă!
57 → 57·10+9 = 579
putere = 10nr. cifre → 9 · 100 + 57 = 957
Cât timp mai sunt cifre, extragi ultima și o prelucrezi. Schimbi doar linia « prelucrez ultima_cifra » → rezolvi altă problemă. Alege limbajul:
Linia « prelucrez ultima_cifra », pentru cele cinci probleme:
Prima aplicare a șablonului: golim numărul cifră cu cifră și le adunăm într-un „coș" numit suma.
| n | — |
| ultima_cifra | — |
| suma | — |
| n | ultima_cifra | suma |
|---|
Schimbi doar linia de prelucrare din schelet — restul rămâne identic. Codul complet, în trei limbaje:
Același schelet, altă prelucrare: cifrele „se mută" din n în inversul — și pentru că ies de la coadă, numărul se răstoarnă.
| n | — |
| ultima_cifra | — |
| inversul | — |
| n | ultima_cifra | inversul |
|---|
Problema-capcană: construiește numărul doar din cifrele pare ale lui n, păstrând ordinea lor. Metoda de la invers nu merge — cifrele ar ieși răsturnate!
| n | — |
| ultima_cifra | — |
| putere | — |
| nr_nou | — |
| ultima_cifra | pară? | putere | nr_nou |
|---|
Un divizor e un număr care îl împarte exact pe n. Întrebarea de aur: până unde are rost să cauți?
Divizorii vin mereu în perechi. Dacă divizor îl împarte exact pe n,
atunci și n / divizor îl împarte. Niciodată nu găsești un divizor singur — vine la pachet cu perechea lui.
Din fiecare pereche, unul e mereu ≤ √n. Dacă amândoi ar fi mai mari decât √n, produsul lor ar depăși n — ceea ce e imposibil, pentru că produsul lor este chiar n.
Deci cauți doar până la √n. Pe cel mic îl găsești căutând, pe cel mare îl primești gratis:
îl calculezi cu o simplă împărțire, n / divizor.
| n | 🐢 verificări până la n | 🐇 verificări până la √n | de câte ori mai puțin |
|---|---|---|---|
| 36 | 36 | 6 | 6 × |
| 10.000 | 10.000 | 100 | 100 × |
| 1.000.000 | 1.000.000 | 1.000 | 1.000 × |
Un număr e prim dacă are exact 2 divizori: 1 și el însuși. Ca să afli dacă n e prim, cauți un divizor între 2 și … până unde? Ambele programe de mai jos sunt corecte și dau același răspuns. Diferă printr-un singur lucru: locul unde se opresc.
prim = (n >= 2).Le punem să facă exact aceeași treabă: să verifice, pe rând, fiecare număr de la 2 până la limita aleasă și să numere câte sunt prime. Răspunsul va fi identic. Timpul — nu.
range(2, n) merge de la 2 până la n − 1 — ultima valoare nu e inclusă, exact ca divizor <= n - 1 din C++.
Iar range(2, int(n ** 0.5) + 1) merge de la 2 până la √n, la fel ca divizor * divizor <= n
(n ** 0.5 este radicalul, iar int(...) taie partea zecimală).divizor * divizor <= n
în loc de divizor <= n - 1 face diferența între „merge" și „ia 100 de puncte". La concurs și la BAC, asta se numește complexitate.Orice număr natural mai mare ca 1 se scrie într-un singur fel ca produs de numere prime — e teorema fundamentală a aritmeticii. Ideea algoritmului: iau cel mai mic factor posibil și împart cu el cât timp se poate, apoi trec la următorul.
| n | — |
| factor | — |
| factor | n % factor | n rămas |
|---|
2 2 2 3 3 5, adică 360 = 2³ · 3² · 5.
Observă că după ce am împărțit de trei ori cu 2, în n nu mai rămâne niciun 2 — de asta factorii ies mereu în ordine crescătoare și toți primi.dacă n > 1 atunci scrie n? Pentru că ne oprim la √n.
Un număr poate avea cel mult un factor prim mai mare decât √n (dacă ar avea doi, produsul lor ar depăși n).
Acel factor nu apucă să fie testat în buclă — dar el este exact ce a rămas în n la final.
Fără linia asta, pentru n = 14 ai afișa doar 2 în loc de 2 7. Este greșeala numărul 1 la această problemă.Cel mai mare divizor comun (cmmdc) — calculat cu scăderi repetate și cu împărțiri repetate, umăr la umăr. Cine termină primul?
Varianta 1 — scăderi repetate
Varianta 2 — împărțiri cu rest
După ce rulezi cursa, aici apare cmmmc(a, b), calculat direct din rezultatul cmmdc-ului. Apasă „Start cursa" 👆
Până acum ai învățat unelte. Acum le folosești ca să te uiți la o întrebare pe care nimeni din lume n-a reușit s-o rezolve — și la care poți contribui cu propriul program.
Christian Goldbach, matematician prusac, îi scrie prietenului său Leonhard Euler o observație aparent banală. Euler îi răspunde și o reformulează în felul în care o știm azi:
Euler i-a răspuns că o consideră „o teoremă absolut sigură, deși nu o pot demonstra". Nici el, nici nimeni după el, nu a reușit. Au trecut 283 de ani.
Fiecare punct din graficul de mai jos e un număr par. Cât de la stânga la dreapta stă punctul îți spune ce număr e; cât de sus stă îți spune în câte feluri se poate scrie ca sumă de două prime. Apasă pe orice punct ca să vezi exact despre ce număr e vorba.
Cerința. Se citește un număr natural n. Pentru fiecare număr par de la 4 până la n, afișează câte perechi de numere prime au suma egală cu acel număr.
O pereche se numără o singură dată: 3+7 și 7+3 sunt aceeași pereche. Perechea 5+5 e validă — cele două prime pot fi egale.
Alege limbajul, lipește codul și apasă „Verifică". Programul rulează chiar în pagină, pe cele 10 teste, exact ca pe pbInfo.
Uneltele de azi — le vei folosi în fiecare modul de acum înainte.