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

Verificare număr prim în C++ (Clasa a IX-a)

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

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

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

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

Dându-se un număr natural n, să se determine dacă este sau nu prim.

Exemplu. Pentru n = 3, răspunsul va fi DA, pe când pentru n = 10, răspunsul va fi NU.

Ce este un număr prim?

Un număr prim este un număr natural care are exact doi divizori: 1 și el însuși.

Câteva curiozități

Numărul 1 nu este prim, deoarece are un singur divizor.

Cel mai mic număr prim este 2. Acesta este singurul număr par și prim.

Determinarea primalității unui număr (metoda naivă)

Un număr prim are exact doi divizori, iar toți divizorii unui număr n se găsesc între 1 și n. Așadar, o primă metodă de rezolvare ar fi să verificăm, pentru toate numerele de la 1 la n, dacă se găsește vreun număr care să fie divizor al lui n:

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int numarDivizori = 0;
    for(int d = 1; d <= n; d++) {
        if(n % d == 0) {
            numarDivizori++;
        }
    }
    if(numarDivizori == 2) {
        cout << "DA";
    } else {
        cout << "NU";
    }
    return 0;
}

Această problemă merge, dar nu este destul de eficientă. Pentru un număr mai mare, spre exemplu 1.000.000.000 (un miliard), s-ar efectua un miliard de operații, un număr imens.

Determinarea primalității unui număr (metoda optimizată 1)

Observăm următorul lucru: divizorii vin în perechi. Astfel, pentru un divizor d al lui n, cu d < sqrt(n), există un alt divizor, d' = n / d, cu proprietatea că d * d' = n și d' > sqrt(n). Prin urmare, putem să parcurgem divizorii doar până la radical, reducând semnificativ numărul de operații efectuate.

Observație. Majoritatea numerelor au un număr par de divizori (din acest motiv vin în perechi). Excepție fac numerele pătrate perfecte — acestea au divizor și pe sqrt(n), care este perechea sa (și care nu trebuie numărată de două ori! — evităm asta prin a verifica dacă n / d == d).

Pentru radical, putem folosi biblioteca <cmath> sau să mergem până când d * d ≤ n.

Implementare C++

Algoritmul este următorul:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int radical = sqrt(n), numarDivizori = 0;
    for(int d = 1; d <= radical; d++) {
        if(n % d == 0) { //Am găsit divizorul d, dar considerăm și perechea acestuia
            int dprim = n / d; //d' = n / d
            if(dprim != d) {
                numarDivizori += 2;
            } else { //Dacă d' == d, atunci perechea lui d este el însuși, deci îl numărăm doar o dată
                numarDivizori++;
            }
        }
    }
    if(numarDivizori == 2) {
        cout << "DA";
    } else {
        cout << "NU";
    }
    return 0;
}

Determinarea primalității unui număr (metoda optimizată 2)

O metodă și mai optimizată este următoarea:

  • verificăm dacă n este par; dacă este și n ≠ 2, atunci nu mai are rost să verificăm divizorii acestuia, deoarece clar nu va fi prim; dacă n este chiar 2, atunci afișăm că este prim;
  • luăm doar divizorii impari până la sqrt(n); n fiind impar, nu mai trebuie să verificăm dacă se împarte la numere pare.

Implementare C++

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    if(n == 2) { //Caz particular: n este 2
        cout << "DA";
    } else if(n < 2) { //Caz particular: n < 2 (nu va fi prim)
        cout << "NU";
    } else if(n % 2 == 0) { //n este > 2. Dacă este par, atunci nu poate fi prim
        cout << "NU";
    } else {
        int gasitDivizori = 0;
        for(int d = 3; d * d <= n; d += 2) { //Luăm divizori impari: 3, 5, 7, …
            if(n % d == 0) { //Am găsit un divizor diferit de 1 și de n, deci n nu este prim
                gasitDivizori = 1;
                break;
            }
        }
        if(gasitDivizori == 1) { //Dacă am găsit divizori diferiți de 1 și de n, atunci nu este prim
            cout << "NU";
        } else { //În sfârșit!!! n e prim 🤑
            cout << "DA";
        }
    }
    return 0;
}

Verifică instant dacă un număr este prim în C++

Mai ții minte Ciurul lui Eratostene? Este o lecție predată la matematică în clasa a șasea, prin care puteam să determinăm foarte ușor pentru primele n numere naturale, care sunt prime.

Ideea este următoarea: știm că 2 este prim, așadar toți multiplii lui 2 (4, 6, 8, …) nu sunt primi — îi marcăm într-un vector. Mergem la următorul număr nemarcat, 3. Asumăm astfel că este prim, așadar multiplii săi îi marcăm (6, 9, 12, …). Mergem la următorul număr nemarcat, 5. Repetăm procedeul și observăm faptul că numerele nemarcate sunt cele prime.

Pentru tot codul complet și explicații amănunțite, vă recomandăm acest articol de la 100din100.

Problemă propusă

# Problemă Dificultate
24. Este prim Ușoară (2 )

Alte resurse și 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

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

© 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