Scrii un program care citește două numere și afișează cel mai mare divizor comun, cel mai mic multiplu comun și dacă sunt prime între ele.
cmmdc.cpp, în consolă
84 120
12 840
NU
Partea a doua a lecției despre while. Dacă n-ai lucrat încă pe cifrele unui număr, începe cu partea întâi, legată la final.
să parcurgi divizorii unui număr
să verifici rapid dacă un număr e prim, până la radical
să calculezi cmmdc cu algoritmul lui Euclid
să afli cmmmc fără să depășești int
Pasul 2 din 5
Rulează-l linie cu linie
Algoritmul lui Euclid pe 48 și 18. Ideea: cmmdc(a, b) e același cu cmmdc(b, a % b), iar numerele scad repede.
euclid.cpp
#include<iostream>usingnamespace std;intmain() {int a, b; cin >> a >> b;while (b != 0) {int r = a % b; a = b; b = r; } cout << a;return0;}
Variabile
Ce apare pe ecran
Linia 5. Două variabile întregi, încă fără valoare.
Linia 6. Se citesc 48 și 18, de pe același rând.
Linia 7. 18 e diferit de 0, deci se intră în buclă.
Linia 8. Restul lui 48 la 18 e 12. r e declarat în buclă și trăiește doar într-o tură.
Linia 9.a ia locul lui b: 18.
Linia 10.b ia restul: 12. Perechea (48, 18) a devenit (18, 12).
Linia 7. 12 ≠ 0, încă o tură.
Linia 8. 18 % 12 = 6.
Linia 9.a devine 12.
Linia 10.b devine 6. Perechea e (12, 6).
Linia 7. 6 ≠ 0, încă o tură.
Linia 8. 12 % 6 = 0: 6 îl împarte exact pe 12.
Linia 9.a devine 6.
Linia 10.b devine 0.
Linia 7.b e 0, bucla se oprește. Rezultatul a rămas în a.
Linia 12. Se afișează 6.
Linia 13.main se încheie.
Gata. Trei ture pentru 48 și 18. Prin scăderi repetate ar fi fost patru, iar diferența crește cu mărimea numerelor.
Prezice ieșirea
Rulezi programul cu 17 și 5. Ce afișează?
Răspuns: „1”.
Perechile sunt (17, 5), (5, 2), (2, 1), (1, 0). 17 e prim, iar 5 nu îl divide, deci singurul divizor comun e 1: numerele sunt prime între ele.
Pasul 3 din 5
Algoritmii cu divizori
Fragmentele stau în main. Toți folosesc același test: n % d == 0 înseamnă „d îl divide pe n”.
1
Toți divizorii
divizori.cpp
int n = 12, d = 1;while (d <= n) {if (n % d == 0) cout << d << ' '; d++;}
Ce apare pe ecran
1 2 3 4 6 12
d ia pe rând valorile de la 1 la n, iar if le păstrează doar pe cele care împart exact. Cu un contor în loc de cout, afli câți divizori are numărul.
2
E prim? Verifici până la radical
prim.cpp
int n = 91, d = 2;bool prim = n >= 2;while (d * d <= n && prim) {if (n % d == 0) prim = false; d++;}cout << prim << ' ' << d - 1;
Ce apare pe ecran
0 7
Dacă n are un divizor mai mare decât radicalul, are și unul mai mic, perechea lui. Ajunge deci să încerci d cât timp d * d <= n. Pentru 91 = 7 · 13, bucla se oprește la 7.
Condiția && prim oprește căutarea la primul divizor găsit. prim pornește de la n >= 2, pentru că 0 și 1 nu sunt prime.
3
cmmdc prin scăderi
scaderi.cpp
int a = 48, b = 18;while (a != b) {if (a > b) a -= b;else b -= a;}cout << a;
Ce apare pe ecran
6
Varianta din manual: scazi mereu numărul mic din cel mare până devin egale. E ușor de urmărit pe hârtie, dar lentă când numerele sunt foarte diferite, de exemplu 1000000 și 1. Nu merge dacă unul dintre numere e 0.
4
cmmmc și long long
cmmmc.cpp
longlong a = 120000, b = 70000;longlong x = a, y = b;while (y != 0) {longlong r = x % y; x = y; y = r;}cout << x << ' ' << a * b / x;
Ce apare pe ecran
10000 840000
cmmmc(a, b) = a · b / cmmdc(a, b). Aici a · b = 8 400 000 000, peste limita unui int, de aproximativ 2,1 miliarde. long long merge până pe la 9 · 1018. Algoritmul lucrează pe copii, ca să-i rămână a și b pentru formulă.
Capcană: 1 iese prim
Dacă pornești cu prim = true, pentru n = 1 bucla nu rulează deloc: 2 · 2 > 1. Nimeni nu schimbă prim:
unu.cpp
#include<iostream>usingnamespace std;intmain() {int n = 1, d = 2;bool prim = true;while (d * d <= n && prim) {if (n % d == 0) prim = false; d++; } cout << prim;return0;}
Ce apare pe ecran
1
Repară cu bool prim = n >= 2;. La bac, testele includ aproape sigur 0 și 1.
Capcană: afișezi variabila greșită
Bucla se oprește exact când b devine 0. Deci, după ea, b e mereu 0:
gresit.cpp
#include<iostream>usingnamespace std;intmain() {int a = 48, b = 18;while (b != 0) {int r = a % b; a = b; b = r; } cout << b;return0;}
Ce apare pe ecran
0
Repară cu cout << a;. Întreabă-te ce valoare are fiecare variabilă în clipa în care condiția devine falsă.
Pasul 4 din 5
Verifică-te
Cinci grile în stilul subiectului I. După fiecare răspuns vezi de ce e așa.
1 din 5 · Prezice ieșirea
Ce afișează programul?
scaderi.cpp
#include<iostream>usingnamespace std;intmain() {int a = 12, b = 8;while (a != b) {if (a > b) a -= b;else b -= a; } cout << a;return0;}
Răspuns: „4”.
(12, 8) devine (4, 8), apoi (4, 4). Numerele sunt egale, bucla se oprește, iar cmmdc e 4.
2 din 5 · Prezice ieșirea
Ce afișează programul?
numara.cpp
#include<iostream>usingnamespace std;intmain() {int n = 36, d = 1, nr = 0;while (d <= n) {if (n % d == 0) nr++; d++; } cout << nr;return0;}
Răspuns: „9”.
Divizorii lui 36 sunt 1, 2, 3, 4, 6, 9, 12, 18, 36. Un pătrat perfect are mereu un număr impar de divizori: 6 e perechea lui însuși.
3 din 5 · Alege varianta
Ce condiție pui în while ca testul de număr prim să facă cât mai puține ture și să rămână corect?
Răspuns: d * d <= n.
Cu <, la n = 49 nu se mai încearcă 7, iar 49 ar ieși prim. n / 2 e corect doar dacă scrii <=, și oricum face mult mai multe ture.
4 din 5 · Prezice ieșirea
Ce afișează programul?
perfect.cpp
#include<iostream>usingnamespace std;intmain() {int n = 28, s = 0, d = 1;while (d < n) {if (n % d == 0) s += d; d++; } cout << s;return0;}
Răspuns: „28”.
Se adună divizorii mai mici decât 28: 1 + 2 + 4 + 7 + 14 = 28. Un număr egal cu suma divizorilor lui proprii se numește perfect.
5 din 5 · Prezice ieșirea
Ce afișează programul?
ture.cpp
#include<iostream>usingnamespace std;intmain() {int a = 10, b = 4, ture = 0;while (b != 0) {int r = a % b; a = b; b = r; ture++; } cout << ture << ' ' << a;return0;}
Răspuns: „2 2”.
(10, 4) devine (4, 2), apoi (2, 0). Două ture, iar cmmdc e 2.
Pasul 5 din 5
Ce ai învățat
n % d == 0 înseamnă că d îl divide pe n. Pe acest test se bazează toți algoritmii cu divizori.
Pentru prim ajunge să încerci divizorii cât timp d * d <= n. 0 și 1 nu sunt prime.
Euclid: r = a % b; a = b; b = r; până când b e 0. Rezultatul e în a.
cmmmc = a · b / cmmdc. Folosește long long când produsul poate trece de 2 miliarde.
Programul complet
cmmdc cu Euclid, pe copii, apoi cmmmc. Împărțirea se face înainte de înmulțire, a / x * b, ca rezultatul intermediar să rămână mic. La final, DA dacă numerele sunt prime între ele.
cmmdc.cpp
#include<iostream>usingnamespace std;intmain() {longlong a, b; cin >> a >> b;longlong x = a, y = b;while (y != 0) {longlong r = x % y; x = y; y = r; } cout << x << ' ' << a / x * b; cout << '\n';if (x == 1) cout << "DA";else cout << "NU";return0;}