Please explain how Trial Division works for Primality Test
- by mister_dani
I came across this algorithm for testing primality through trial division I fully understand this algorithm
static boolean isPrime(int N) {
if (N < 2)
return false;
for (int i = 2; i <= Math.sqrt(N); i++)
if (N % i == 0)
return false;
return true;
}
It works just fine. But then I came across this other one which works just as good but I do not fully understand the logic behind it.
static boolean isPrime(int N) {
if (N < 2)
return false;
for (int i = 2; i * i<N; i++)
if (N % i == 0)
return false;
return true;
}
It seems like i *i < N behaves like i <= Math.sqrt(N). If so, why?