questions on a particular algorithm
- by paul smith
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)?
