Jump to content

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


Andreigl
 Share

Recommended Posts

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 by shanker'
adaugare exemplu
Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.