Divizibilitate, numere prime, algoritmul lui Euclid

Pe scurt

1 minesențialul, de recitit oricând

Culorile din lecție:termencifră, datăidee-cheie

• n%d==0 înseamnă că d îl divide pe n. Pe asta se construiesc toate problemele din lecție.
• Pentru numere mari, verifici divizorii doar până la radical: d*d<=n.
• Cel mai mare divizor comun se obține cu algoritmul lui Euclid, în două forme: cu rest și cu scăderi. Amândouă apar în lucrări.
• Tema apare la ambele specializări: secvențe de completat la Subiectul I, algoritmi la II.1, cerințe de program la III.1.

Urmează · 1 min

Divizori, apoi numele oficial

4 min

Când împarți 36 la 3, restul e 0, deci 3 e divizor al lui 36. Când îl găsești pe 3, l-ai găsit și pe 12, adică 36/3. Divizorii vin în perechi, iar din fiecare pereche, cel mic e cel mult radicalul lui n.

s=0;
for(d=1;d*d<n;d++)
  if(n%d==0)
    s=s+d+n/d;
if(d*d==n) s=s+d;

Secvența calculează suma divizorilor. Ultima linie tratează pătratele perfecte: la 36, divizorul 6 trebuie adunat o singură dată.

Oficial: la BAC 2021, sesiunea august, SN, I.5, se cere exact expresia care completează s=s+....., iar răspunsul e i+n/i (varianta c, 4 p). În lucrarea din iulie 2024, varianta 3, III.1, enunțul definește divizorii proprii ca divizorii naturali „diferiți de 1 și de el însuși”. Citește mereu definiția din enunț: ea decide dacă numeri 1 și n.

Ultima linie e chiar BAC specială 2024, SN, I.4: bucla for(d=1;d<=x;d++) cu z=d pe ramura comună lasă în z cel mai mare divizor comun (varianta b, 4 p).

Urmează · 4 min

Numere prime

2 min o întrebare la final

Un număr e prim dacă are exact doi divizori naturali. Cauți un divizor între 2 și radical. Dacă nu există, numărul e prim.

ok=1;
if(n<2) ok=0;
for(d=2;d*d<=n;d++)
  if(n%d==0) ok=0;

Oficial: iunie 2026, varianta 3, SN, I.5

if(n%2==0)
  if(n==2) ok=1;
  else ok=0;
else
{ d=......; ok=1;
  while(ok==1 && d*d<=n)
    if(n%d==0) ok=0;
    else d=d+2;
}

Se cere constanta cu care ok devine 1 doar dacă n e prim. Răspunsul e 3 (varianta d, 4 p). Numerele pare au fost tratate deja, deci sunt suficienți divizorii impari: 3, 5, 7... Cu d=1, n%1 e mereu 0, iar ok ar deveni 0 pentru orice număr impar. Cu d=2, s-ar verifica doar 2, 4, 6..., iar 9 ar ieși prim.

Un detaliu pe care enunțul nu îl spune: pentru n=1, bucla nu rulează, iar ok rămâne 1. Enunțul cere „dacă și numai dacă numărul e prim”, iar secvența e cea dată, deci răspunsul din barem rămâne d. În programele tale, tratează separat n<2.

Urmează · 2 min

Factorii primi

4 min

Împarți cât timp se poate la d, apoi treci la d+1. Când ajungi la un d care îl divide pe n, el e sigur prim: divizorii lui mai mici au fost scoși deja.

Oficial: sesiunea specială 2026, varianta 4, II.1 (MI și SN)

citește n (număr natural nenul)
nr←0; d←2
┌cât timp d*d≤n execută
│ p←0
│┌cât timp n%d=0 execută
││ p←1; n←[n/d]
│└■
│ nr←nr+p; d←d+1
└■
┌dacă n≠1 atunci
│ nr←nr+1
└■
scrie nr

La final n=13, deci nr crește: se afișează 3 (6 p). Algoritmul numără factorii primi distincți: 2, 5 și 13. La b) se cer două numere din [10,99] pentru care se afișează 1 (3 p fiecare). Baremul acceptă orice putere a unui număr prim, de forma x la k cu k>0, de exemplu 16 sau 25.

Același tipar, la rezerva din 2025, varianta 7, MI, II.1, reține ultimul factor prim și produsul factorilor distincți: pentru 252 se afișează 7 42 (3 p pentru fiecare valoare).

Urmează · 4 min

Algoritmul lui Euclid

5 min 2 întrebări la final

Ai două bare, de 12 și de 18. Vrei cea mai lungă unitate cu care se măsoară exact amândouă. Dacă unitatea le măsoară pe amândouă, măsoară și diferența lor, 6. Așa poți înlocui bara mare cu ce rămâne din ea.

Forma cu rest funcționează și când x<y: primul pas doar schimbă valorile între ele. Forma cu scăderi nu se termină dacă una dintre valori e 0 și cealaltă nu.

Oficial: patru itemi de 4 p la Subiectul I, SN

Ultimul rând se bazează pe relația cmmmc(x,y)=x*y/cmmdc(x,y). Produsul se calculează înainte de buclă, pentru că bucla schimbă x și y.

Oficial: model 2026, II.1, SN

citește m,n (numere naturale, 1<m<n)
┌repetă
│ x←m; y←n; n←n-1
│┌repetă
││┌dacă x>y atunci x←x-y
│││altfel y←y-x
││└■
│└până când y=0
└până când x≠1
scrie n+1

Pentru 27 și 38 se afișează 36 (6 p). Bucla interioară e Euclid cu scăderi: când x și y devin egale, y←y-x îl face pe y 0, iar x rămâne cmmdc-ul. Bucla exterioară coboară de la n până la primul număr care nu e prim cu m. 38 și 37 sunt prime cu 27, iar cmmdc(27,36)=9. Pentru m=5 și rezultatul 10, baremul acceptă orice n din [10,14] (3 p fiecare).

Urmează · 5 min

Oficial: simulare 2026, III.1, cel mai mic multiplu comun

3 min

Un raft are trei polițe, de lățimi x, y, z din [10,100]. Pe fiecare se pun cuburi cu latura egală cu lățimea poliței, iar polița trebuie umplută complet. Se cere lungimea minimă a poliței. Pentru 40, 20, 30, răspunsul e 120.

Dacă treci prin povestea din enunț, rămâne: un număr divizibil cu x, y și z, cât mai mic. Adică cel mai mic multiplu comun. Numele subprogramului este depozit.

int depozit(int x,int y,int z)
{ int L=x;
  while(L%y!=0 || L%z!=0)
    L=L+x;
  return L;
}

Pornești de la x și mergi din x în x, deci L e mereu multiplu de x. Primul care e divizibil și cu y și cu z e cel mai mic. Valoarea nu depășește 100*100*100, deci încape în int.

La științele naturii se cere aceeași problemă, în pseudocod, la aceeași sesiune.

Urmează · 3 min

Oficial: model 2027, III.1, divizori comuni

3 min

Un teren de x pe y se împarte în parcele pătrate cu latură naturală. Pentru fiecare variantă se scrie numărul de parcele, apoi latura. Pentru 18 și 24: 432 cu latura 1;108 cu latura 2;48 cu latura 3;12 cu latura 6;.

Latura trebuie să dividă și lățimea, și lungimea, deci e divizor comun. Parcele sunt x/d pe un rând și y/d pe celălalt.

void parcele(int x,int y)
{ int d;
  for(d=1;d<=x && d<=y;d++)
    if(x%d==0 && y%d==0)
    { cout<<(x/d)*(y/d);
      cout<<" cu latura "<<d<<";";
    }
}

La științele naturii, aceeași problemă se scrie în pseudocod, cu barem de 10 p: citire 1, valori 5, scriere 2, structuri de control și corectitudine 2.

Urmează · 3 min

Oficial: rezervă 2026, varianta 5, MI, III.1

2 min

O broșură are p pagini, cu p prim, iar catalogul are 3*p pagini. Subprogramul pagini primește n din [2,10⁴] și returnează 1 dacă toate cele n pagini formează un astfel de set. Pentru 44 răspunsul e 1 (11+33), iar pentru 48 sau 27 e 0.

Totalul e p+3*p=4*p. Deci n trebuie să fie multiplu de 4, iar n/4 să fie prim.

int pagini(int n)
{ int p,d;
  if(n%4!=0) return 0;
  p=n/4;
  if(p<2) return 0;
  for(d=2;d*d<=p;d++)
    if(p%d==0) return 0;
  return 1;
}

Barem: antet 2 p; proprietate verificată 6 p, câte 1 p pentru identificarea unui divizor, algoritmul de numărare sau verificare, divizorii analizați pentru număr prim, cazul n=4, multiplu de 4, asocierea celor două condiții; returnare 1 p; variabile locale și corectitudine globală 1 p.

Urmează · 2 min

Ce se cere la BAC

3 mincum apare la examen

Urmează · 3 min

Greșeli care costă puncte

1 mincapcanele de evitat

• d*d<n la testul de primalitate: 25 și 49 ies prime. Condiția corectă e d*d<=n.
• 1 considerat prim. Baremul de la rezervă 2026 punctează separat cazul acesta.
• x și y folosiți după Euclid, când au alte valori.
• x*y înainte de a verifica domeniul: la valori mari, produsul poate depăși int.
• Scăderi cu valoare nulă: nu se termină bucla.
• Un divizor pătrat adunat de două ori la suma divizorilor în perechi.
• Mesaj sau format diferit: la model 2027, afișarea corectă, dar fără expresia cerută, ia 1 p din 2.

Urmează · 1 min