Divizorii unui numar - tutorial incepatori in C++
Publicat la 18 martie 2020 · algoritmi olimpiada clasa 9 cpp
Prezentul articol te va ajuta să îndeplineşti diferite aplicații cu divizorii unui număr.
Trebuie cunoscută parcurgerea divizorilor unui număr, înainte de toate, ca să ne asigurăm că ştim să rezolvăm alte probleme.
ATENȚIE! Formulele nu trebuie reținute, ci deduse.
Parcurgerea divizorilor unui număr
Ne propunem, înainte de toate, să înțelegem cum facem rost de fiecare divizor în parte înainte de a aplica diferite operații cu acestea.
Vom lua pe rând fiecare metodă în parte, de la algoritmul naiv la cel eficient.
Algoritmul naiv
Ştim clar că pentru un număr natural n, orice divizor d aparține [1; n]. Astfel, algoritmul naiv se bazează pe parcurgerea tuturor numerelor de la 1 la n şi verificarea n % d == 0:
//Parcurgere//pentru mai multe detalii: https://100din100.netlify.app
for(int d = 1; d <= n; d++) {
if(n % d == 0) { //am găsit un divizor//pentru mai multe detalii: https://100din100.netlify.app
cout<<d<<" ";
}
}
Este evident că pentru valori mari ale lui n, de exemplu 1.000.000.000, programul iese din timp. Aşadar, ce alte îmbunătățiri putem face?
Algoritmul eficient
Observăm că pentru fiecare divizor d ≤ sqrt(n), există o pereche a sa, n / d ≥ sqrt(n). Aşadar în loc să parcurgem toate numerele din [1; n], parcurgem doar de la 1 la sqrt(n) şi efectuăm operația dorită atât pe d, cât şi pe n / d.
//Parcurgere//pentru mai multe detalii: https://100din100.netlify.app
int d;
for(d = 1; d * d < n; d++) {
if(n % d == 0) { //am găsit doi divizori//pentru mai multe detalii: https://100din100.netlify.app
cout<<d<<" "<<n / d<<" ";
}
}
if(d * d == n) { //Numărul este pătrat perfect, prelucrăm şi radicalul.//pentru mai multe detalii: https://100din100.netlify.app
cout<<d<<" ";
}
Parcurgerea divizorilor primi
În cazul în care vrem să parcurgem doar divizorii primi ai unui număr, putem să ne bazăm pe următorul principiu: parcurgem numere de la 2 (primul număr prim) până la sqrt(n). Dacă întâlnim un divizor, îl prelucrăm şi împarțim repetat, până nu mai putem, pe n la divizorul determinat d. Se garantează mereu că atunci când găsim un nou divizor, va fi prim, demonstrabil prin reducere la absurd:
să zicem că am întâlnit un nou divizor care nu este prim, d. Atunci d se poate scrie ca şi p1 * p2 * ... * pk, unde orice pi (1 ≤ i ≤ k) este prim. Evident p1, p2, ..., pk sunt toate ≤ d. Asta înseamnă că am mai întâlnit numerele p1, p2, ..., pk înaintea lui d, aşadar n nu este divizibil cu niciun p1, p2, ..., pk (pentru că am împarțit n la fiecare număr, vezi mai sus). Rezultă că ipoteza a fost falsă.
Astfel, ajungem la următorul algoritm:
//Parcurgere//pentru mai multe detalii: https://100din100.netlify.app
for(int d = 2; d * d <= n; d++) {
if(n % d == 0) { //am găsit un divizor prim//pentru mai multe detalii: https://100din100.netlify.app
cout<<d<<" ";
while(n % d == 0) n /= d;
}
}
if(n > 1) { //foarte important! dacă până la radical//pentru mai multe detalii: https://100din100.netlify.app
//nu am reuşit să facem n = 1 (adică nu am găsit//pentru mai multe detalii: https://100din100.netlify.app
//divizori primi), atunci n este prim şi afişăm.//pentru mai multe detalii: https://100din100.netlify.app
cout<<n<<" ";
}
Aplicații cu divizori
Numărul de divizori
Când găsim un divizor, îl contorizăm (facem o variabilă nr şi scriem nr++;).
Observație. Putem să ne folosim de anumite formule ca să aflăm unele rezultate mai repede; de exemplu, numărul de divizori al unui număr este defapt produsul succesorilor exponenților divizorilor primi. Aşadar, iată un algoritm mai eficient:
int nr = 1;
for(int d = 2; d * d <= n; d++) {
int exponent = 0;
while(n % d == 0) n /= d, exponent++;
nr *= (exponent + 1);
//observăm că dacă nu se împarte n la d,//pentru mai multe detalii: https://100din100.netlify.app
//atunci nr se înmulțeşte cu 1, adică nu se modifică.//pentru mai multe detalii: https://100din100.netlify.app
}
if(n > 1)
nr *= 2;
cout<<nr;
Suma divizori
Când găsim un divizor, îl adunăm (facem o variabilă nr şi scriem nr += d;).
Primul tau program, variabile si operatii - TUTORIAL COMPLET C++
Eşti elev de liceu şi nu înțelegi informatica? Acest clip ar trebui să te ajute să înțelegi cele mai elementare aspecte privind informatica de liceu - algoritmica...
Rezolvări probleme PbInfo
Problemele de informatică pot fi dificile uneori, şi este util să vedem o soluție bună pentru a ne autoverifica. De multe ori sunt necesare doar nişte modificări minore, de aceea este bine să analizăm soluțiile bune cu atenție!
Video - Probleme Rezolvate PbInfo
Aici gasiti rezolvarea mai multor probleme de pe site-ul pbinfo.ro, în format video, pe canalul nostru de YouTube.
Tipuri de date in C++ si C - Tutorial Incepatori
De ce avem nevoie de date?
În timp ce lucrăm cu valori, avem nevoie (uneori chiar suntem siliți!) să memorăm datele undeva, în memorie. Prin intermediul variabilelor putem accesa o zonă de …
Al doilea cel mai mic/mare element al unui sir in C++
Dându-se un şir de numere naturale distincte, aflați al doilea cel mai mic număr din şir.
Exemplu:Intrare
9 5 8 2 4
Ieşire
4
Explicație4 este al doilea cel mai mi…
Vectori caracteristici si vectori de frecventa - Materie Olimpiada Informatica C++
Ce este un vector de frecvență sau un vector caracteristic?
Vectorii caracteristici rețin dacă un element se află într-un vector sau nu. Similar, vectorii de frecvență rețin numărul de apar…
Smenul lui Mars (Difference Arrays) in C++
Ce este Şmenul lui Mars?
Să zicem că avem un şir a[] cu n elemente. Unele probleme cer efectuarea unor operații de tipul sum(st, dr, val), cu semnificația că adunăm la …
Afişare cu 2 zecimale exacte, fără şi cu rotunjire - TUTORIAL C++
Tutorialul acesta te învață cum să afişezi un număr real cu mai multe zecimale exacte. Multe probleme cer...
Algoritmi elementari - video
Tutoriale uşor de urmărit, sub forma unor videoclipuri!
Cautarea binara pentru olimpiada in C++
Ce este căutarea binară?
Să zicem că ai un vector a[] cu n elemente crescătoare. Căutarea binară este un algoritm eficient care determină dacă orice număr x apare sau n…
Verifica daca o data este valida in C++
Dându-se o dată (zi lună an), trebuie verificat dacă data este validă sau nu.
Exemplu:Intrare
zi = 3, luna = 4, an = 2021
Ieşire
DA
Pentru a verifica da…
Divizorii unui numar - tutorial incepatori in C++
Prezentul articol te va ajuta să îndeplineşti diferite aplicații cu divizorii unui număr.
Trebuie cunoscută parcurgerea divizorilor unui număr, înainte de toate, ca să ne asigurăm că ştim s…
Primul program - Operatori si expresii - Tutorial incepatori C++
Alcătuirea unui program pentru rezolvarea unei probleme se rezumă defapt la rezolvarea unor probleme mai mici. Spre exemplu, pentru a afla suma numerelor prime dintr-un şir, trebuie să ştim cum …
Sume partiale. Suma elementelor dintr-o submatrice in C++
Cu ce ne ajută sumele parțiale?
Unele probleme cer aflarea sumei elementelor unei secvențe dintr-un şir dat. Metoda naivă, care face suma tuturor elementelor din secvența cerută, deobicei n…
Ciurul lui eratostene - generarea numerelor prime - olimpiada C++
Să zicem că vrem să aflăm dacă mai multe numere sunt sau nu prime. Desigur, putem aplica algoritmul de aflare a numărului de divizori pentru toate numerele, doar că dacă avem foarte multe şi sun…
Ridicarea la putere in timp logaritmic pentru olimpiada in C++
Un număr de forma b la puterea e nu poate fi calculat precum celelalte operații (adunarea, scăderea, înmulțirea, împărțirea) pur şi simplu. În articolul acesta vom prezenta un mod foarte …
Verifica daca un an este bisect in C++
Dându-se un an, trebuie verificat dacă este un an bisect sau nu.
Exemplu:Intrare
2021
Ieşire
NU
Definiția anului bisect
Deşi pare evident, anii bis…
Ce este coada/queue si cum functioneaza? Tutorial clasa a 10-a
Ce este coada?
Coada (Queue din engleză) este o structură de date liniară care funcționează prin inserarea elementelor noi la spate şi prin eliminarea elementelor doar prin față. Altfel spu…
Sortarea vectorilor si a structurilor (pentru incepatori) in C++
Sortarea în informatică reprezintă procesul de a ordona un şir de obiecte (numere, caractere, sau chiar şiruri) după un anumit criteriu.
Spre exemplu, putem ordona crescător sau descrescăto…
Prelucrarea cifrelor unui numar pentru incepatori in C++
Acest articol urmăreşte aplicarea diferitelor aplicații cu cifrele unui număr: suma cifrelor, numărul de cifre, oglinditul unui număr ş.a.m.d. Puteți găsi multe probleme care cer prelucrarea cif…
Tablelul ASCII - clasa a X-a - char C++
Ce este tabelul ASCII?
Calculatorul reține numere (valori de 1 şi de 0), aşadar a fost nevoie de o corespondență între numere şi caractere pentru a putea reprezenta litere, si…
Citirea si Afisarea in fisiere in C++ - Tutorial Incepatori
De ce citirea din fişier?
De multe ori este necesară citirea şi afişarea în fişier, unul din motive fiind faptul că nu trebuie să reintroducem datele de intrare de fiecare dată când rulăm p…
Creeaza un joc 2D in PYTHON pentru incepatori - Capitolul 0 (Instalare)
Care-i faza?
În aceste câteva tutoriale vom învăța cum să îți creezi propriul joc video în Python. Puteți viziona atât pe YouTube, cât şi în format text pe site-ul nostru (aici adică).
…
Parcurgerea matricei in spirala in C++
Cu ce ne ajută parcurgerea matricei pătratice în spirală?
În concursuri şi olimpiade apar probleme legate de parcurgerea matricei în spirală. Deşi ideea de bază este destul de uşoară, algor…