Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Afișarea divizorilor primi ai unui număr în C++

Dându-se un număr natural n, să se afișeze pe ecran divizorii primi ai acestuia, precum și puterile din descompunere.

Exemplu. Pentru n = 20, se va afișa 22, 51 (deoarece 20 = 22 * 51 = 4 * 5).

Explicarea algoritmului

Procedăm astfel: luăm primul divizor al lui n, asumăm că este un număr prim și îl împărțim pe n la el până când nu se mai poate (contorizând numărul de împărțiri). Astfel, am determinat primul divizor prim și prima putere (pe care le afișăm) și știm sigur că n acum nu se mai împarte la divizorul acesta. Repetăm procedeul cu următoarele numere, până când trecem de radicalul lui n.

De ce este divizorul curent mereu prim?

Se garantează că divizorul curent va fi prim. Să demonstrăm prin absurd: să zicem că întâlnim un divizor neprim al lui n, să îl notăm d. Numărul d, fiind compus (neprim), poate fi descompus ca produs de numere prime (pe care le-am notat p1, p2, …, pk):

https://i.ibb.co/km0CD7x/image.png

Dacă n se împarte la d, înseamnă că n se împarte și la divizorii primi ai lui d, adică la p1, p2, …, pk. Cum aceste numere sunt clar mai mici decât d, înseamnă că le-am mai întâlnit înainte, când parcurgeam divizorii primi ai lui n. Dacă i-am întâlnit, înseamnă că l-am împărțit pe n la fiecare dintre aceste numere până când nu mai puteam, așadar n nu se mai împarte la niciunul dintre divizorii primi ai lui d. Așadar, n nu se poate împărți la d. Cum am zis că d este divizor al lui n, ipoteza este falsă, așadar toți divizorii d vor fi numere prime.

Alte observații

Este posibil ca și după parcurgerea cu for, să rămână o valoare în n. Această valoare va fi categoric un număr prim, așadar adăugăm la descompunerea noastră, la final, n1.

Implementare în C++

Iată rezolvarea în C++, folosind explicațiile menționate mai sus:

#include <iostream>

using namespace std;

int main()
{
    //Citim și declarăm numărul n
    int n;
    cin >> n;

    //Parcurgem divizorii primi
    for(int d = 2; d * d <= n; d++) { //Începem de la 2, ne interesează doar divizorii primi
        if(n % d == 0) { //Am găsit un divizor prim
            int putere = 0;
            while(n % d == 0) { //Cât timp se împarte n la acest divizor, creștem puterea
                putere++;
                n = n / d;
            }
            cout << d << "^" << putere << " ";
        }
    }
    if(n > 1) { //Caz particular, când n mai conține un număr prim la final
        cout << n << "^1";
    }
    return 0;
}

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Matrice pătratice în C++. Diagonala principală și secundarăCel mai semnificativ bit în C++Inversarea unui vector în C++Oglinditul recursiv al unui număr în C++Recursivitate în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Combinatorică în C++: permutări, aranjamente, combinări și alteleCiurul lui Eratostene în C++Ce înseamnă endl în C++?Afișarea elementelor unui vector recursiv în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Rădăcina cubică a unui număr în C++ (cube root)Funcții în C++. Ce sunt subprogrameleValoarea absolută (modulul) unui număr în C++Inversarea unui șir de caractere în C++Mediana unui șir de valori în C++Află secolul unui an citit de la tastatură în C++Interclasarea a doi vectori în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Do while vs while în C++ - Care e diferența?Cifra maximă a unui număr recursiv în C++Copiuțe: Cifrele unui numărVectorii în C++: citire și afișareAl N-lea termen dintr-o progresie aritmeticăRidicarea la putere în timp logaritmic în C++. Exponențiere rapidăVerificarea unui an bisect în C++Numere triunghiulare. Verificarea unui număr triunghiularInstrucțiunea de decizie în C++: if, else, switch, caseAlgoritm recursiv pentru căutare binară (clasa a X-a)Ce este o funcție void în C++?Verificare dacă șir de caractere este palindrom în C++Instrucțiunea while (structuri repetitive)Citirea și afișarea matricelor în C++Instrucțiunea do while (structuri repetitive)Numărul minim de peroane pentru o gară în C++Vectorii în C++: declarare și parcurgereCăutare binară în C++Divide et Impera (metodă de programare C++)Șiruri de caractere în C++. Tot ce trebuie să știiCifra maximă și minimă a unui număr în C++Suma numerelor naturale dintr-un interval dat în C++Oglinditul unui număr în C++Cum să afișezi partea întreagă a unui număr real în C++Transformarea unui număr din baza 10 în baza 2 în C++Transformarea unui număr din baza 2 în baza 10 în C++Cifra de control a unui numărMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleStructuri repetitive (while, do while, for, etc)Numărul de divizori primi ai unui număr în C++Operații cu numere mari în C++ - Toate funcțiile explicateVerifică dacă un număr aparține șirului Fibonacci în C++Prima cifră a unui număr în C++Instrucțiunea continue (structuri repetitive)Factorialul unui număr în C++Suma divizorilor unui număr în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă un număr dat este o putere de 2 în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Bordarea unei matrice în C++Verifică dacă un caracter este cifră în C++Șirul lui Fibonacci în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Pointer în C++. Variabile de tipul char * (char steluță)Instrucțiunea break (structuri repetitive)Suma elementelor unui vector recursiv în C++Cel mai puțin semnificativ bit în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorTransformarea unei litere mari în literă mică în C++Citește un șir de caractere cu spații în C++Maximul și minimul a n valori în C++Verifică dacă un caracter este literă în C++Transformarea unei litere mici în literă mare în C++Generarea șirului Fibonacci generalizat în C++Verifică dacă trei puncte sunt coliniare C++Codul ASCII (tabel complet)Distanța dintre două puncte în C++Comentarii în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Maximul și minimul a trei valori în C++Cea mai lungă secvență de elemente crescătoare în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Instrucțiunea for (structuri repetitive)CMMDC recursiv a două numere naturale în C++Ce este o variabilă unsigned în C++?Indicatorul lui Euler în C++Numărul de divizori al unui număr în C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortAfișarea divizorilor primi ai unui număr în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicCalculul combinărilor de n luate câte k (nCk) în C++Aflarea sumei primelor N sume GaussNumărul de cifre ale factorialului unui numărVerificare dacă un număr este palindrom în C++Numărul combinărilor în C++ (formula combinărilor)Complexitatea unui algoritm (timp și spațiu) în C++Maximul și minimul unui vector în C++Cum să calculezi instant 2 la puterea N în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Verificare număr prim în C++ (Clasa a IX-a)Al N-lea termen Fibonacci în C++Radicalul unui număr în C++ (rădăcina pătrată)Tipul struct în C++. Ce sunt structurile de date neomogeneCel mai frecvent element dintr-un șir în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiNumărul de apariții al unui număr într-un vector în C++Verifică dacă o literă este vocală în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Tipuri de date în C++: numere întregi, reale, caractere și alteleCifrele unui număr. Prelucrarea cifrelor unui număr în C++Maximul și minimul a două valori în C++Aria și circumferința unui cerc în C++Cel mai mic număr cu suma cifrelor N în C++Câte numere naturale sunt într-un interval dat? (C++)Suma 1 + 2 + 3 + ... + N în C++Aria unui triunghi folosind coordonatele acestora în C++Verifică dacă o literă este mică sau mare în C++Verifică dacă un număr este par sau impar fără modulo în C++Cum să citești și să afișezi în fișiere în C++Numărul permutărilor în C++ (formula permutărilor)Al N-lea termen dintr-o progresie geometricăInterschimbarea a două variabile în C++ (3 metode)Ce înseamnă variabilă globală și locală în C++?Vectori de frecvență (de apariții) în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont