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

Numărul de divizori primi ai unui număr în C++

Dându-se un număr natural n, să se afișeze pe ecran numărul de divizori primi ai acestuia.

Exemplu. Pentru n = 20, se va afișa 2 (deoarece 20 = 22 * 51, adică are 2 divizori primi).

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 în acest caz adunăm 1 la numărul de divizori primi.

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
    int nrdivprim = 1;
    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
            nrdivprim++;
            while(n % d == 0) { //Cât timp se împarte n la acest divizor, îl împărțim pe n
                n = n / d;
            }
        }
    }
    if(n > 1) { //Caz particular, când n mai conține un număr prim la final
        nrdivprim++;
    }

    //Afișăm numărul răspuns
    cout << nrdivprim;
    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

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

© 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