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

Indicatorul lui Euler în C++

Ce este indicatorul lui Euler

Indicatorul lui Euler al unui număr n, notat cu φ(n) sau phi(n), reprezintă numărul de numere mai mici sau egale cu n și totodată prime cu acesta. Spre exemplu, phi(4) = 2, deoarece singurele numere mai mici sau egale cu 4 și prime cu acesta sunt 1 și 3.

Exemple

Iată valorile lui phi(n), pentru 1 ≤ n ≤ 15. Se observă că pentru un număr prim p, phi(p) = p - 1.

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
φ(n) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8

Cum se determină indicatorul lui Euler al unui număr n

Fie p1, p2, …, pk factorii primi ai lui n. Atunci, phi(n) are următoarea formulă:

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

Prin urmare, vom crea o variabilă phi, inițial egală cu numărul nostru n, după care vom găsi divizorii primi ai lui n folosim algoritmul clasic, pe care l-am învățat în această lecție. Pentru fiecare divizor prim, vom reclacula valoarea phi. La final, determinăm corect valoarea phi.

Implementare C++

Cu această observație, implementarea în C++ este:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    int phi = n;
    for(int d = 2; d * d <= n; d++) {
        if(n % d == 0) { //Am găsit un divizor prim
            phi = phi / d * (d - 1);
            while(n % d == 0)
                n /= d;
        }
    }
    if(n > 1) {
        phi = phi / n * (n - 1);
    }
    cout << phi;
    return 0;
}

Cum se determină indicatorii lui Euler pentru numerele de la 1 la n

Vom utilza un algoritm similar cu cel al ciurului lui Eratostene. Ciurul lui Eratostene este un algoritm important care ia numeroase forme, însă la bază poate să determine pentru orice număr de la 1 la n, care sunt prime. Puteți citi mai multe despre acest algoritm (și să urmăriți implementarea) pe această pagină.

Algoritmul de mai jos se folosește de formula matematică a lui phi(n). Dacă știm factorii primi ai unui număr, atunci avem formula:

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

Unde p1, p2, …, pk sunt factorii primi ai lui n.

Prin urmare, vom salva în ciur valoarea n, iar de fiecare dată când întâlnim o valoare primă i, vom luat toți multiplii j ai săi, astfel încât i este un factor prim al lui j. Vom înmulți phi(j) cu (i - 1) / i.

Implementare C++

Iată codul care implementează ideea de mai sus:

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că numărul de numere prime cu i și mai mici ca acesta este i

    for(int i = 2; i <= n; i++)
        if(ciur[i] == i) {
            for(int j = i; j <= n; j += i)
                ciur[j] = ciur[j] / i * (i - 1);
        }

    //Afișăm la final indicatorul numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Alte resurse sau bibliografie

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

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

© 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