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 al numerelor de la 1 la N (Folosind ciurul lui Eratostene)

Dându-se un număr natural n, să se afișeze pe ecran indicatorii lui Euler ale tuturor numerelor de la 1 la n.

Exemplu. Pentru n = 10, indicatorii sunt 1, 1, 2, 2, 4, 2, 6, 4, 6, 4 (1 are indicatorul 1, 2 are indicatorul 1, 3 are indicatorul 2, etc.).

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.

Vom prezenta o metodă ce se bazează pe algoritmul ciurului lui Eratostene.

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

Vom utiliza 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:

Formulă pentru phi(n)

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

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