PROGRAMOWANIE I ALGORYTMY

szkoła fraktal
Zapraszamy na zajęcia

Badanie czy liczba jest pierwszą


powrót

Zacznijmy od definicji liczby pierwszej. Liczba pierwsza to taka liczba naturalna większa od 1, której jedynymi naturalnymi dzielnikami jest liczba 1 i ona sama. Oto kilka początkowych liczb pierwszych:

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ ...$$

Warto zauważyć, że takich liczb jest nieskończenie wiele.

Aby określić, czy dana liczba jest pierwsza należy zbadać jej dzielniki. Dla zadanej liczby n sprawdzamy kolejne liczby naturalne należące do przedziału:

$$[2...\sqrt{n}]$$

Jeśli któraś z tych liczb jest dzielnikiem, oznacza to, że nasza liczba nie jest pierwsza.

Dlaczego wystarczy sprawdzić tylko liczby od 2 do pierwiastka z n ?

Przeanalizujmy kilka przykładów i wypiszmy dzielniki dla następujących liczb: 24, 25 i 31.

$$\sqrt{24}\approx 4,9$$

$$D_{24}=\{1,\ 2,\ 3,\ 4,\ |4,9|,\ 6,\ 8,\ 12,\ 24\}$$

$$\sqrt{25}= 5$$

$$D_{25}=\{1,\ \overbrace{5}^{|5|}\ 25\}$$

$$\sqrt{31}\approx 5,6$$

$$D_{24}=\{1,\ |5,6|,\ 31\}$$

Warto zauważyć, że jeśli liczba n ma dzielniki większe od 1, to będzie ich tyle samo po lewej i prawej stronie $$\sqrt{n}.$$W przypadku liczb kwadratowych takich jak np. $$25,$$pierwiastek z tej liczby będzie jej dzielnikiem.

Wynika to z faktu, że jeśli liczba d jest dzielnikiem liczby n to zachodzi zależność:

$$k = n/d\Rightarrow d = n/k$$

np.

$$6 = 24/4 \Rightarrow 4 = 24/6$$

Rozwiązanie w C++:

/*****************www.algorytm.edu.pl****************/
#include<iostream>
using namespace std;

bool czy_pierwsza(int n)
{
	if(n<2)
		return false; //gdy liczba jest mniejsza niż 2 to nie jest pierwszą
		
	for(int i=2;i*i<=n;i++)
		if(n%i==0)
			return false; //gdy znajdziemy dzielnik, to dana liczba nie jest pierwsza
	return true;
}

int main()
{
	int n;
	
	cout<<"Podaj liczbę: ";
	cin>>n;
	
	if(czy_pierwsza(n)) //lub czy_pierwsza(n)==1
		cout<<"Liczba "<<n<<" jest pierwsza"<<endl;
	else
		cout<<"Liczba "<<n<<" nie jest pierwsza"<<endl;
	
	return 0;
}