liczby pierwsze c++

Question

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

Witam mam pytanie odnosnie kodu z pewnej strony internetowej, a mianowicie nie potrafie zrozumiec tej petli for  for(int i=2;i*i<=n;i++) if(n%i==0) i byłbym wdzieczny gdyby ktos mi to wytlumaczyl 

Answer 1

Zacznijmy od 

if(n%i==0)

ten warunek zwraca prawdę tylko wtedy gdy n jest podzielne przez i, (% to operator reszty z dzielenia, kiedy reszta z dzielenia to zero to n jest podziele przez i), a to znaczy że liczba nie jest liczbą pierwszą.

Pętla

for(int i=2;i*i<=n;i++)

to pętla szukająca wszystkich liczb które mogą dzielić n. Pętla kończy swoje działanie gdy i * i > n, czyli inaczej i > sqrt(n) (pierwiastkowanie z obu stron, zakładamy że n > 0). Innymi słowy pętla zaczyna przy i = 2 i kończy gdy i przekorczy pierwiastek z n.

Jeżeli liczba jest liczbą złożoną to na pewno ma dzielnik mniejszy bądź równy swojemy pierwiastkowi. Wynika to z tego że jeżeli istnieje czynnik większy od pierwiastka n to musi istnieć też mniejszy (np. 36 = 3 * 12, 3 < 6 a 12 > 6).

Mam nadzieje że pomogłem, pozdrawiam.

Answer 2

Pętlę zaczynamy od wartości i=2

Warunek i*i<n jest optymalizacją. Jeżeli liczba i po podniesieniu do kwadratu jest większa od n liczby to to kolejne liczby na pewno nie będą dzielnikami liczby n.

Operator % w C/C++ zwraca resztę z dzielenia. Jeżeli liczba n po podzieleniu przez i nie daje reszty (innymi słowy reszta jest równa zero) to liczba jest n jest podzielna przez i.