[C++] Verificarea unui număr dacă este prim sau nu

[Andreigl]

Un număr prim este acel număr care se împarte doar la 2 numere și anume 1 și el însuși.

Cea mai eficientă metodă pentru a verifica dacă un număr este prim sau nu este următoarea:

bool isPrim(long long int Numar)
{
	if (Numar == 2)
		return true;

	if (Numar % 2 == 0 or Numar < 2)
		return false;

	for (int contor = 3; contor * contor <= Numar; contor+=2)
		if (Numar % contor == 0)
			return false;

	return true;
}

 

Cum este gândită? Ei bine cum am zis, un număr prim are doar 2 divizori. 

De reținut este că un număr par nu este niciodată un număr prim. Singurul număr par care este prim în același timp este 2. De ce? Ei bine, are doar 2 divizori.

Deci cum am scăpat de o gamă largă de numere, mai avem decât să facem un începând de la 3, până la radicalul acestuia. Contorul îl însuma din 2 în 2.

De ce începem de la 3 și nu de la 2? Pentru că nu vrem să împărțim numărul nostru la numere pare. Dacă observați, în for vor fi doar deîmpărțitori impari.

 

Exemplu cum să apelați funcția de mai sus:

#include <iostream>

bool isPrim(long long int Numar)
{
	if (Numar == 2)
		return true;

	if (Numar % 2 == 0 or Numar < 2)
		return false;

	for (int contor = 3; contor * contor <= Numar; contor += 2)
		if (Numar % contor == 0)
			return false;

	return true;
}

int main()
{
	int input; std::cin >> input;

	if (isPrim(input))
		std::cout << "Numarul citit este un numar prim";
	else
		std::cout << "Numarul citit nu este un numar prim";
}

 

Edited January 24, 2020 by shanker'
adaugare exemplu

[Jackson Brooklyn]

5. Limbajul de programare in care a fost scris tutorialul trebuie scris intre paranteze patrate - Extras din: 

 

Simplu si curat, felicitari! Multumim pentru tutorial.

 

Edited January 8, 2020 by Jackson Brooklyn