M13 | L12 – L13 – CMMDC si CMMMC

Astăzi vom afla despre:

  • Cel mai mare divizor comun

Aplicațiile pe care le vom folosi sunt:

Code Blocks

PROIECTE:

Probleme: https://www.pbinfo.ro/

Lectia 12

Din punct de vedere matematic, cel mai mare divizor comun a două numere naturale a şi b este un număr natural d, care:

  • divide şi pe a şi pe b:
  • este divizibil cu orice divizor a lui a şi b.

Pentru a afla cel mai mare divizor comun al două sau mai multor numere naturale mai mari decât 1 se procedează astfel:

  • se descompun numerele în factori primi
  • se iau toţi factorii primi comuni, o singură dată, la puterea cea mai mică şi se înmulţesc între ei.

Exemplu:

Dacă a = 420 atunci descompunerea în factori primi este 420=22*3*5*7 şi dacă b = 504 atunci descompunerea în factori primi este 504=23*32*7, de unde rezultă că cel mai mare divizor comun dintre cele două numere, notat cmmdc(420, 504)= 22*3*7=84

Pentru a scrie un algoritm care determină valoarea celui mai mare divizor comun dintre două numere după modelul matematic de determinare este destul de complicat. Există algoritmi mai simpli pentru realizrea acestui lucru:

Algoritmul lui Euclid:

    Cel mai mic multiplu comun dintre două numere naturale a şi b, notat cmmmc(a,b) se calculează cu relaţia:

    • a*b/cmmdc(a,b)

    Aplicatie: Se citesc de la tastatură n numere naturale. Se cere să se determine cel mai mare divizor comun dintre cele n numere.

    Lectia 13

    1. Se dau două numere naturale a şi b. Dacă cele două numere sunt prime între ele, atunci să se calculeze suma cifrelor celor două numere, altfel să se descompună în factori primi numărul mai mare.

    Exemplu: Dacă a= 84 şi b=180, nu sunt numere prime între ele, cmmdc(84,180)=12 şi pe ecran se va afişa descompunerea în factori primi al numărului mai mare 22*32*5.

    Dacă a=85 şi b=87, sunt prime între ele şi pe ecran va fi afişat 28=8+5+8+7

    1. Afişaţi toate numere prime din intervalul [a, b], unde a şi b sunt două numere naturale mai mici de 10000, şi a<=b.

    Exemplu: dacă a a=10 şi b=20 numerele prime din intervalul [10,20] sunt 11, 13, 17 şi 19.

    1. Se citeşte un număr natural n,(n<=10000) care nu este număr prim. Se cere să se determine care este cel mai mare număr prim, dar mai mic decât n şi care este cel mai mic număr prim dar mai mare cu n.

    Exemplu: dacă n este 100, cel mai mare numar prim mai mic decăt 100 este 97, iar cel mai mic număr prim mai mare decât 100 estr 101.

    1. Să se determine toate numerele perechile de numere prime gemene mai mici decât un număr natural n, citită de la tastatură (n<=10000). Două numere formează o pereche de numere prime gemenene.

    Exemple: dacă n=20 atunci se vor afişa perechile (3, 5), (5, 7), (11, 13), (17, 19).

    1. Se citeşte de la tastaură un număr natural n(n<=10000). Se cere să se afişeze primele n numere prime.

    Exemplu: dacă n=10 atunci primele 10 numere prime sunt 2,3,5,7,11,13,17,19, 23,29.

    1. Se citeşte de la tastaură un număr natural n, (n<=10000). Se cere să calculeze suma numerelor divizibile la 3 mai mici sau egale cu n.

    Exempl: dacă n=16 atunci se va afişa 45, s= 3+6+9+12+15=45.

    1. Determinaţi şi afişaţi pe ecran toate numere naturale care împărţite la 24, 30,18 dau restul 7.

    Exemplu: dacă n=2000 se vor afişa numerele 367, 727, 1087, 1447, 1807.

    1. Se dau două numere naturale a şi b. Să se afişeze toţi divizorii comuni celor două numere.

    Exemplu: dacă a=180 şi b=84 atunci se vor afisa 1, 2, 3, 4, 6, 12.

    1. Se citesc două numere naturale a şi b. Se cere să se determine dacă sunt numere prime între ele.

    Exemplu: Dacă a= 84 şi b=180, nu sunt numere prime între ele, cmmdc(84,180)=12 iar dacă a=85 şi b=87, sunt prime între ele.

    1. Se citeşte de la tastatură un număr natural n, Să se determine cel mai mic număr natural are are are exact n divizori.

    Exemplu: dacă n=4 atunci se va afişa 6 care are 4 divizori 1, 2, 3, 6.