Q:

questions on a particular algorithm

Upon searching for a fast primr algorithm, I stumbled upon this:

public static boolean isP(long n) { 
    if (n==2 || n==3) return true; 
    if ((n&0x1)==0 || n%3==0 || n<2) return false; 
    long root=(long)Math.sqrt(n)+1L;
    // we check just numbers of the form 6*k+1 and 6*k-1 
    for (long k=6;k<=root;k+=6) { 
        if (n%(k-1)==0) return false; 
        if (n%(k+1)==0) return false; 
    } 
    return true; 
}

My questions are:

Why is long being used everywhere instead of int? Because with a long type the argument could be much larger than Integer.MAX thus making the method more flexible?
In the second 'if', is n&0x1 the same as n%2? If so why didn't the author just use n%2? To me it's more readable.
The line that sets the 'root' variable, why add the 1L?
What is the run-time complexity? Is it O(sqrt(n/6)) or O(sqrt(n)/6)? Or would we just say O(n)?

A:

Yes, there is no other reason I can see why they would choose long over int.
It is the same, but it's one of the clever things developers (especially with an embedded-C background) do to shave off a few CPU cycles between applying a mask over a long and applying modulo. The developer probably thought that the jitted bytecode going to the CPU will carry the trick, thus making his algorithm 0.000...00005% faster (note that the trick is not even in the loop) at the expense of having people wtf all the time.
Either readability, or the developer thought that since + is evaluated right-to-left, forcing the rightmost constant to be long (1L) - given that the result is long - may be faster. The generated bytecode will likely push 1 to the stack (as long with 1L or as int with 1), evaluate the sqrt, pop-cast-push the sqrt, and then do a ladd (long addition). It's unlikely there is a real gain, especially since, again, you're not in the loop, and since usually the jitter is smart.
The big-O complexity is O(sqrt(n)) or O(n^(1/2)) - a multiplicative constant over n is irrelevant in theory. Saying O(n) is not wrong (big-O is an upper boundary), but it's not really useful either, because O(sqrt(n)) is a much better estimator (you try to estimate the upper bound as close to running time as possible, to a constant).

edit: saying it's O(n) is indeed wrong, given the definition of big-O.

A:

I suppose you are right, the author wants to gain extra flexibility. 
This is somewhat a matter of taste. If you are used to bit arithmetic, the & form is readable, too. The usage of 0x1 indicates this. The author could have used 0b1 or 01 or 1. But if you frequently mingle your bits, you eventually start using hex as it is based on 2. BTW, don't think that this is an optimization. Operations with constants are very easy to optimize and compilers will do so. E.g. (n * 32) will be translated to (n << 5).
You only have to check all numbers that are less or equal to the root of the candidate number. But the algorithm checks only numbers of the form 6k - 1 and 6k + 1. At least that is what the author says in the comment. But the k from the comment is not the long k from the code. Instead long k takes values of the form 6 * i. Based on this the possible prime factors are computed. Now if 6i - 1 is a prime factor, you have to make sure, that k runs up to (including) 6i. E.g suppose your (long) Math.sqrt(n) can be written as 6*i - 1. But it is computed as k-1, so k has to run up to 6i, which is (long) Math.sqrt(n) + 1.
An alternative without +1 is thus:
public static boolean isP2(long n) { 
    if (n==2 || n==3 || n==5) return true;
    if ((n&0x1)==0 || n%3==0 || n<2 || n%5==0) return false; 
    long root=(long)Math.sqrt(n);
    // we check just numbers of the form 6*i+1 and 6*i-1 
    for (long k=6;k<=root;k+=6) { 
        if (n%(k+5)==0) return false; 
        if (n%(k+1)==0) return false; 
    } 
    return true; 
}

The complexity is O(sqrt(n)), which is actually the same as O(sqrt(n) / 6). But as 6 is a constant, we can ignore it in Big-O-Notation. Same goes for O(sqrt(n/6)), it's just harder to see. The reason is
sqrt(n/6) = (n/6)^0.5 = n^0.5 / 6^0.5
And 6 ^ 0.5 is just another constant. However O(n) is definitely wrong.

