Może ktoś mi wytłumaczyć warunek:
for(int i=2;i*i<=n;i++)
if(n%i==0)
bo go nie rozumiem
0
0
Liczba pierwsza dzieli się przez 1
i przez samą siebie.
Więc jeżeli dla liczby n
znajdziesz dzielnik, który nie jest 1
albo n
, to nie jest to liczba pierwsza.
Dodatkowo nie ma sensu sprawdzać dzielników większych niż pierwiastek kwadratowy z n
. Bo jeżeli by taki istniał, to dawałby wynik dzielenia, który byłby mniejszy od tego pierwiastka, a ten z kolei zostałby znaleziony we wcześniejszej iteracji.
1
Dodam jeszcze czytankę:
https://en.wikipedia.org/wiki/Primality_test