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: 153

Filed under:
|
|

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

Related posts about java

Related posts about algorithm