Please explain how Trial Division works for Primality Test
Posted
by
mister_dani
on Stack Overflow
See other posts from Stack Overflow
or by mister_dani
Published on 2013-11-02T21:35:28Z
Indexed on
2013/11/02
21:53 UTC
Read the original article
Hit count: 206
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?
© Stack Overflow or respective owner
