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

Cel mai mic/mare divizor prim 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 cel mai mic (sau mare) divizor prim al tuturor numerelor de la 1 la n.

Exemplu. Pentru n = 10, divizorii primi cei mai mici ale numerelor de la 1 la n sunt -, 2, 3, 2, 5, 2, 7, 2, 3, 2(1 nu are divizori primi, 2 are cel mai mic divizor 2, 3 are cel mai mic divizor 3, etc.).

Vom prezenta o metodă ce se bazează pe algoritmul 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.

Putem să adaptăm un pic algoritmul: pentru numărul curent i, dacă este prim, vom lua toți multiplii săi j, și vom spune modifica cel mai mic sau cel mai mare divizor prim al lui n.

Cel mai mic divizor prim al numerelor de la 1 la n

Asumăm pentru început că cel mai mic divizor prim al tuturor numerelor sunt chiar ele însuși. Iterăm printre numerele prime (cele care au cel mai mic divizor prim egal cu ele însuși). Când găsim un astfel de număr i, îi luăm multiplii săi (numiți j) și verificăm dacă aceste numere au fost modificate sau nu (adică dacă încă au elementul din ciur egale cu ele însuși). Pentru cele care nu au fost modificate încă (adică numerele neprime — deoarece sunt multipli de i —, dar în ciur încă nemodificate), vom seta în ciur elementul i, marcând faptul că am găsit cel mai mic divizor prim al numărului j. Dacă mai găsim în viitor un alt număr care îl are pe j ca multplu, nu îi mai putem modifica valoarea.

#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ă elementul i are cel mai mic divizor prim pe el însuși

    for(int i = 2; i <= n; i++) //Pentru toate numerele de la 2 la n
        if(ciur[i] == i) { //Elementul i este prim
            for(int j = 2 * i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
                if(ciur[j] == j)
                    ciur[j] = i;
        }

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

Cel mai mare divizor prim al numerelor de la 1 la n

Asumăm pentru început că cel mai mare divizor prim al tuturor numerelor sunt chiar ele însuși. Iterăm printre numerele prime (cele care au cel mai mare divizor prim egal cu ele însuși). Când găsim un astfel de număr i, îi luăm multiplii săi (numiți j) și setăm valoarea din ciur la i. Deoarece luăm i-urile crescătoare, de fiecare dată când modificăm valoarea ciur[j], numărul nou este garantat să fie mai mare — astfel vom găsi cel mai mare divizor prim.

#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ă elementul i are cel mai mic divizor prim pe el însuși

    for(int i = 2; i <= n; i++) //Pentru toate numerele de la 2 la n
        if(ciur[i] == i) { //Elementul i este prim
            for(int j = 2 * i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
                ciur[j] = i;
        }

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

© 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