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,\ ...$$

• Zobacz 1000 kolejnych liczb pierwszych,
• Zobacz 10000 kolejnych liczb pierwszych,
• Zobacz 100000 kolejnych liczb pierwszych.

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;
}