100din100

Verifica daca un numar este prim in C++

Publicat la 09 iulie 2020 · algoritmi clasa 9 cpp


Există multe aplicații în C++ care cer verificarea primalității unui număr. O modalitate este să generezi toate numerele prime până la un număr dat şi după aceea să verifici dacă este sau nu în şir. Însă, dacă avem numere mai mari, nu putem folosi Ciurul lui Eratostene, căci avem nevoie de un vector mai lung, aşadar suntem siliți să verificăm individual dacă un număr este sau nu este prim.

Cuprinsul lecției

Algoritm de verificare

Ideea este simplă: căutăm posibili divizori (ca aici) şi dacă nu găsim niciun divizor, înseamnă că este număr prim.

Asta înseamnă că trebuie să parcurgem de la 2 până la radicalul numărului. Aşa ar arăta algoritmul:

bool e_prim = true; //presupunem inițial că este prim.//pentru mai multe detalii: https://100din100.netlify.app
for(int d = 2; d * d <= n; d++) {
	if(n % d == 0) { //pisici! am găsit un divizor. Nu e număr prim.//pentru mai multe detalii: https://100din100.netlify.app
		e_prim = false;
		break;
	}
}
if(e_prim) cout<<"e prim!";
else cout<<"nu e prim :(";

Optimizare

În fond, nu este nevoie să verificăm numerele pare. Dacă numărul pe care îl testăm se divide cu un număr par, automat se divide şi cu 2, aşadar putem doar să punem un if la început şi după aceea să luăm doar numerele impare:

#include <cmath>
bool e_prim = true; //presupunem inițial că este prim.//pentru mai multe detalii: https://100din100.netlify.app
if(n % 2 == 0) {
	e_prim = false;
} else {
	for(int d = 3; d <= sqrt(n); d = d + 2) {
		if(n % d == 0) { //pisici! am găsit un divizor. Nu e număr prim.//pentru mai multe detalii: https://100din100.netlify.app
			e_prim = false;
			break;
		}
	}
}
if(e_prim) cout<<"e prim!";
else cout<<"nu e prim :(";

Alte articole

Primul tau program, variabile si operatii - TUTORIAL COMPLET C++

Eşti elev de liceu şi nu înțelegi informatica? Acest clip ar trebui să te ajute să înțelegi cele mai elementare aspecte privind informatica de liceu - algoritmica...

Rezolvări probleme PbInfo

Problemele de informatică pot fi dificile uneori, şi este util să vedem o soluție bună pentru a ne autoverifica. De multe ori sunt necesare doar nişte modificări minore, de aceea este bine să analizăm soluțiile bune cu atenție!

Video - Probleme Rezolvate PbInfo

Aici gasiti rezolvarea mai multor probleme de pe site-ul pbinfo.ro, în format video, pe canalul nostru de YouTube.

Tipuri de date in C++ si C - Tutorial Incepatori

De ce avem nevoie de date? În timp ce lucrăm cu valori, avem nevoie (uneori chiar suntem siliți!) să memorăm datele undeva, în memorie. Prin intermediul variabilelor putem accesa o zonă de …

Verifica daca un an este bisect in C++

Dându-se un an, trebuie verificat dacă este un an bisect sau nu. Exemplu:Intrare 2021 Ieşire NU Definiția anului bisect Deşi pare evident, anii bis…

Vectori caracteristici si vectori de frecventa - Materie Olimpiada Informatica C++

Ce este un vector de frecvență sau un vector caracteristic? Vectorii caracteristici rețin dacă un element se află într-un vector sau nu. Similar, vectorii de frecvență rețin numărul de apar…

Tablelul ASCII - clasa a X-a - char C++

Ce este tabelul ASCII? Calculatorul reține numere (valori de 1 şi de 0), aşadar a fost nevoie de o corespondență între numere şi caractere pentru a putea reprezenta litere, si…

Afişare cu 2 zecimale exacte, fără şi cu rotunjire - TUTORIAL C++

Tutorialul acesta te învață cum să afişezi un număr real cu mai multe zecimale exacte. Multe probleme cer...

Algoritmi elementari - video

Tutoriale uşor de urmărit, sub forma unor videoclipuri!

Creeaza un joc 2D in PYTHON pentru incepatori - Capitolul 0 (Instalare)

Care-i faza? În aceste câteva tutoriale vom învăța cum să îți creezi propriul joc video în Python. Puteți viziona atât pe YouTube, cât şi în format text pe site-ul nostru (aici adică). …

Sortarea vectorilor si a structurilor (pentru incepatori) in C++

Sortarea în informatică reprezintă procesul de a ordona un şir de obiecte (numere, caractere, sau chiar şiruri) după un anumit criteriu. Spre exemplu, putem ordona crescător sau descrescăto…

Parcurgerea matricei in spirala in C++

Cu ce ne ajută parcurgerea matricei pătratice în spirală? În concursuri şi olimpiade apar probleme legate de parcurgerea matricei în spirală. Deşi ideea de bază este destul de uşoară, algor…

Smenul lui Mars (Difference Arrays) in C++

Ce este Şmenul lui Mars? Să zicem că avem un şir a[] cu n elemente. Unele probleme cer efectuarea unor operații de tipul sum(st, dr, val), cu semnificația că adunăm la …

Divizorii unui numar - tutorial incepatori in C++

Prezentul articol te va ajuta să îndeplineşti diferite aplicații cu divizorii unui număr. Trebuie cunoscută parcurgerea divizorilor unui număr, înainte de toate, ca să ne asigurăm că ştim s…

Cautarea binara pentru olimpiada in C++

Ce este căutarea binară? Să zicem că ai un vector a[] cu n elemente crescătoare. Căutarea binară este un algoritm eficient care determină dacă orice număr x apare sau n…

Verifica daca o data este valida in C++

Dându-se o dată (zi lună an), trebuie verificat dacă data este validă sau nu. Exemplu:Intrare zi = 3, luna = 4, an = 2021 Ieşire DA Pentru a verifica da…

Citirea si Afisarea in fisiere in C++ - Tutorial Incepatori

De ce citirea din fişier? De multe ori este necesară citirea şi afişarea în fişier, unul din motive fiind faptul că nu trebuie să reintroducem datele de intrare de fiecare dată când rulăm p…

Ciurul lui eratostene - generarea numerelor prime - olimpiada C++

Să zicem că vrem să aflăm dacă mai multe numere sunt sau nu prime. Desigur, putem aplica algoritmul de aflare a numărului de divizori pentru toate numerele, doar că dacă avem foarte multe şi sun…

Prelucrarea cifrelor unui numar pentru incepatori in C++

Acest articol urmăreşte aplicarea diferitelor aplicații cu cifrele unui număr: suma cifrelor, numărul de cifre, oglinditul unui număr ş.a.m.d. Puteți găsi multe probleme care cer prelucrarea cif…

Sume partiale. Suma elementelor dintr-o submatrice in C++

Cu ce ne ajută sumele parțiale? Unele probleme cer aflarea sumei elementelor unei secvențe dintr-un şir dat. Metoda naivă, care face suma tuturor elementelor din secvența cerută, deobicei n…

Ce este coada/queue si cum functioneaza? Tutorial clasa a 10-a

Ce este coada? Coada (Queue din engleză) este o structură de date liniară care funcționează prin inserarea elementelor noi la spate şi prin eliminarea elementelor doar prin față. Altfel spu…

Primul program - Operatori si expresii - Tutorial incepatori C++

Alcătuirea unui program pentru rezolvarea unei probleme se rezumă defapt la rezolvarea unor probleme mai mici. Spre exemplu, pentru a afla suma numerelor prime dintr-un şir, trebuie să ştim cum …

Ridicarea la putere in timp logaritmic pentru olimpiada in C++

Un număr de forma b la puterea e nu poate fi calculat precum celelalte operații (adunarea, scăderea, înmulțirea, împărțirea) pur şi simplu. În articolul acesta vom prezenta un mod foarte …

Al doilea cel mai mic/mare element al unui sir in C++

Dându-se un şir de numere naturale distincte, aflați al doilea cel mai mic număr din şir. Exemplu:Intrare 9 5 8 2 4 Ieşire 4 Explicație4 este al doilea cel mai mi…

Învață să programezi gratis!

Am lansat InfoAs, o platformă de informatică cu sute de probleme, lecții și concursuri, totul gratuit. Încearcă acum!

Probleme PbInfo Rezolvate

Rezolvare FactorialQuery (#3512)
Rezolvare Caractere (#1335)
Rezolvare Stampile (#3560)
Rezolvare Urare (#941)
Rezolvare asii (#1260)
Rezolvare uciv (#1273)
Rezolvare Globuri (#813)
Rezolvare Copii2 (#3178)
Rezolvare Parc2 (#3179)
Rezolvare Camioane (#2263)
Rezolvare Icsuri (#1751)
Rezolvare ZOO (#2637)
Rezolvare Nevricos (#2292)

Articole începători

Creeaza un joc 2D in PYTHON pentru incepatori - Capitolul 0 (Instalare)
Vectori caracteristici si vectori de frecventa - Materie Olimpiada Informatica C++
Prelucrarea cifrelor unui numar pentru incepatori in C++
Tablelul ASCII - clasa a X-a - char C++
Tipuri de date in C++ si C - Tutorial Incepatori
Primul program - Operatori si expresii - Tutorial incepatori C++
Al doilea cel mai mic/mare element al unui sir in C++
Verifica daca o data este valida in C++
Verifica daca un an este bisect in C++
Generarea sirului Fibonacci in C++

Articole algoritmi

Cautarea binara pentru olimpiada in C++
Ciurul lui eratostene - generarea numerelor prime - olimpiada C++
Vectori caracteristici si vectori de frecventa - Materie Olimpiada Informatica C++
Divizorii unui numar - tutorial incepatori in C++
Parcurgerea matricei in spirala in C++
Ridicarea la putere in timp logaritmic pentru olimpiada in C++
Smenul lui Mars (Difference Arrays) in C++
Sortarea vectorilor si a structurilor (pentru incepatori) in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Ce este coada/queue si cum functioneaza? Tutorial clasa a 10-a
Al doilea cel mai mic/mare element al unui sir in C++
Verifica daca o data este valida in C++
Verifica daca un an este bisect in C++
Generarea sirului Fibonacci in C++
Verifica daca un numar este prim in C++

Toate articolele

Acasă
Cautarea binara pentru olimpiada in C++
Ciurul lui eratostene - generarea numerelor prime - olimpiada C++
Creeaza un joc 2D in PYTHON pentru incepatori - Capitolul 0 (Instalare)
Vectori caracteristici si vectori de frecventa - Materie Olimpiada Informatica C++
Divizorii unui numar - tutorial incepatori in C++
Parcurgerea matricei in spirala in C++
Prelucrarea cifrelor unui numar pentru incepatori in C++
Ridicarea la putere in timp logaritmic pentru olimpiada in C++
Smenul lui Mars (Difference Arrays) in C++
Sortarea vectorilor si a structurilor (pentru incepatori) in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Tablelul ASCII - clasa a X-a - char C++
Tipuri de date in C++ si C - Tutorial Incepatori
Ce este coada/queue si cum functioneaza? Tutorial clasa a 10-a
Primul program - Operatori si expresii - Tutorial incepatori C++
Citirea si Afisarea in fisiere in C++ - Tutorial Incepatori
Al doilea cel mai mic/mare element al unui sir in C++
Verifica daca o data este valida in C++
Verifica daca un an este bisect in C++
Generarea sirului Fibonacci in C++
Verifica daca un numar este prim in C++
Probleme rezolvate PbInfo - Explicatii PbInfo
Vezi solutiile corecte instant pe PbInfo
Politica de confidentialitate (privacy policy)

Articole olimpiadă

Cautarea binara pentru olimpiada in C++
Ciurul lui eratostene - generarea numerelor prime - olimpiada C++
Vectori caracteristici si vectori de frecventa - Materie Olimpiada Informatica C++
Divizorii unui numar - tutorial incepatori in C++
Ridicarea la putere in timp logaritmic pentru olimpiada in C++
Smenul lui Mars (Difference Arrays) in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Ce este coada/queue si cum functioneaza? Tutorial clasa a 10-a
Citirea si Afisarea in fisiere in C++ - Tutorial Incepatori

Articole C++

Cautarea binara pentru olimpiada in C++
Ciurul lui eratostene - generarea numerelor prime - olimpiada C++
Vectori caracteristici si vectori de frecventa - Materie Olimpiada Informatica C++
Divizorii unui numar - tutorial incepatori in C++
Parcurgerea matricei in spirala in C++
Prelucrarea cifrelor unui numar pentru incepatori in C++
Ridicarea la putere in timp logaritmic pentru olimpiada in C++
Smenul lui Mars (Difference Arrays) in C++
Sortarea vectorilor si a structurilor (pentru incepatori) in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Tablelul ASCII - clasa a X-a - char C++
Tipuri de date in C++ si C - Tutorial Incepatori
Ce este coada/queue si cum functioneaza? Tutorial clasa a 10-a
Primul program - Operatori si expresii - Tutorial incepatori C++
Citirea si Afisarea in fisiere in C++ - Tutorial Incepatori
Al doilea cel mai mic/mare element al unui sir in C++
Verifica daca o data este valida in C++
Verifica daca un an este bisect in C++
Generarea sirului Fibonacci in C++
Verifica daca un numar este prim in C++
Vezi solutiile corecte instant pe PbInfo
Adăugăm constant postări noi!

Toate articolele

Acasă
Cautarea binara in C++
Ciurul lui eratostene - generarea numerelor prime
Divizorii unui numar in C++
Parcurgerea matricei in spirala in C++
Prelucrarea cifrelor unui numar in C++
Ridicarea la putere in timp logaritmic in C++
Smenul lui Mars (Difference Arrays) in C++
Sortarea vectorilor si a structurilor in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Tablelul ASCII - char C++
Tipuri de date in C++ si C
Ce este coada/queue si cum functioneaza?
Primul program - Operatori si expresii - elemente de baza ale limabjului C++
Citirea si Afisarea in fisiere in C++
Verifica daca un numar este prim in C++
Probleme rezolvate PbInfo - Explicatii PbInfo
Vezi solutiile corecte instant pe PbInfo
Politica de confidentialitate (privacy policy)

Articole clasa a 9-a

Cautarea binara in C++
Ciurul lui eratostene - generarea numerelor prime
Divizorii unui numar in C++
Parcurgerea matricei in spirala in C++
Prelucrarea cifrelor unui numar in C++
Ridicarea la putere in timp logaritmic in C++
Smenul lui Mars (Difference Arrays) in C++
Sortarea vectorilor si a structurilor in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Tablelul ASCII - char C++
Tipuri de date in C++ si C
Primul program - Operatori si expresii - elemente de baza ale limabjului C++
Citirea si Afisarea in fisiere in C++
Verifica daca un numar este prim in C++

Articole clasa a 10-a

Ce este coada/queue si cum functioneaza?

Articole C++

Cautarea binara in C++
Ciurul lui eratostene - generarea numerelor prime
Divizorii unui numar in C++
Parcurgerea matricei in spirala in C++
Prelucrarea cifrelor unui numar in C++
Ridicarea la putere in timp logaritmic in C++
Smenul lui Mars (Difference Arrays) in C++
Sortarea vectorilor si a structurilor in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Tablelul ASCII - char C++
Tipuri de date in C++ si C
Ce este coada/queue si cum functioneaza?
Primul program - Operatori si expresii - elemente de baza ale limabjului C++
Citirea si Afisarea in fisiere in C++
Verifica daca un numar este prim in C++
Vezi solutiile corecte instant pe PbInfo

Articole algoritmi

Cautarea binara in C++
Ciurul lui eratostene - generarea numerelor prime
Divizorii unui numar in C++
Parcurgerea matricei in spirala in C++
Ridicarea la putere in timp logaritmic in C++
Smenul lui Mars (Difference Arrays) in C++
Sortarea vectorilor si a structurilor in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Ce este coada/queue si cum functioneaza?
Verifica daca un numar este prim in C++

Articole începători

Prelucrarea cifrelor unui numar in C++
Tablelul ASCII - char C++
Tipuri de date in C++ si C
Primul program - Operatori si expresii - elemente de baza ale limabjului C++

Articole olimpiadă

Cautarea binara in C++
Ciurul lui eratostene - generarea numerelor prime
Divizorii unui numar in C++
Ridicarea la putere in timp logaritmic in C++
Smenul lui Mars (Difference Arrays) in C++
Sume partiale. Suma elementelor dintr-o submatrice in C++
Ce este coada/queue si cum functioneaza?
Citirea si Afisarea in fisiere in C++
Adăugăm constant postări noi!

🍪 Politca cookie şi de confidențialitate

Pentru a oferi o experiență mai bună, utilizăm cookie-uri şi alte tehnologii similare pe site-ul nostru. Continuând navigarea pe 100din100, confirmați că sunteți de acord cu utilizarea lor şi că ați citit şi sunteți de acord cu politica de confidențialitate