Why we can use sqrt(n) instead of n/2 as an upper bound while finding prime numbers?

Question

How we can use sqrt(n) instead of n/2 in this code? Is it correct to use sqrt(n)?

    static boolean isPrime(long n)
{
    if(n<=1) return false;
    double limit = Math.sqrt(n);
    for(long i = 2; i <= limit; i++)
    {
        if(n%i==0) return false;
    }
    return true;
}

Don't use `i++` as that's wasteful: you only need to iterate over the primes. — Bathsheba, Jan 27 '14 at 14:30
In some cases (n < 4), n/2 will be smaller than sqrt (n). In all the other cases, the algorithm with n/2 bound would be correct but factor sqrt(n)/2 slower — Niklas B., Jan 27 '14 at 14:31
@Bathsheba? How the hell do you know which numbers are prime? Without precomp this is the best you can do apart from constant optimizations like skipping every even number. — Niklas B., Jan 27 '14 at 14:32
One way: call the function! Block the recursion by storing the first few primes. — Bathsheba, Jan 27 '14 at 14:33
@NiklasB. You know all even numbers except 2 are NOT prime. So you can safely use `i+=2` instead of `++i`. — KitsuneYMG, Jan 27 '14 at 14:47
@KitsuneYMG that's the kind of constant optimization i was talking about. — Niklas B., Jan 27 '14 at 14:52
@Bathsheba you will still need to check all the other numbers if `n` is prime. The bound doesn't improve, it's still O(sqrt (n)) and trial division is in fact very fast if you only use it on a few numbers because it doesn't need memory access at all. — Niklas B., Jan 27 '14 at 14:54
If you do more than a few checks, you don't use trial division anyway, so why bother about constant optimizations... — Niklas B., Jan 27 '14 at 14:59

gefei · Answer 1 · 2014-01-27T14:35:30.573

9

if n is not a prime, say n = p * q, then p and q cannot be both greater than sqrt(n) (otherwise p*q would be greater than n)

edited Jan 27 '14 at 14:35

answered Jan 27 '14 at 14:26

gefei

18,922
9
50
67

I think you used "n" when you meant "x" a couple of times. – Patricia Shanahan Jan 27 '14 at 14:31

score 1 · Answer 2 · answered Jan 27 '14 at 14:38

The shown algorithm checks for every integer between 2 and sqrt(n) if n is divisible by it. If n was divisible by a number greater than sqrt(n), say a, then there would be a factor b so that a * b = n and b < a. In this case the algorithm will find b "first" and see that n is not prime.

Therefore it is not necessary to check any number > sqrt(n).

score 0 · Answer 3 · edited Feb 23 '16 at 08:51

Perhaps the code would be more understandable (and faster) if you wouldn't use sqrt().

for (long i = 2; i*i <= n; i = (i==2) ? 3 : i+2) {
    ....
}

Consider ii > n, and n is divisible by i, so that n/i = m. Then m must be smaller than i. But this means your loop must have encountered m earlier already, and found that n is divisible by m. So this means that you find all divisors of n by looping through the range 2..k, where kk <= n.

If you compute a list of prime numbers, you can also take advantage of the fact that if n is not prime, it must be divisible by a prime number. Hence it suffices to check only prime numbers lower or equal than sqrt(n). Since there are much less prime numbers than ordinary numbers in the range, your code will run even faster. You can take the prime numbers from the part of the list you have already computed.

Why we can use sqrt(n) instead of n/2 as an upper bound while finding prime numbers?

3 Answers3

Linked