Java Prime Checker

Question

if found a prime checker in java, which uses this method. Can somebody explain, why the for-loop goes to the square root of the searched prime number? - Is there a more efficient way of doing this? - Thank you!

    public static boolean isPrime(int p){ 
            if(p % 2 == 0 || p < 2){ 
                return false; 
            }  
            else {  
                System.out.println("Sqare: " + (int)Math.sqrt(p));
                for(int i = 3; i <= (int)Math.sqrt(p); i = i+2){ 
                    if(p % i == 0){  
                        return false; 
                    }
                }
            } 

            return true;  
}

Possible duplicate of [Why do we check up to the square root of a prime number to determine if it is prime?](http://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr) — denvercoder9, Dec 11 '16 at 17:54
Also, check these out: http://stackoverflow.com/questions/1801391/what-is-the-best-algorithm-for-checking-if-a-number-is-prime http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers — denvercoder9, Dec 11 '16 at 17:56
Try to dry run the code, if you want to understand the code. Take different numbers and try to run on them. Or try in debugging Environment. — Faraz Sultan, Dec 11 '16 at 18:01
Just noticed, the code fails when `p` = 2. The initial `if` statement needs adjusting. Something like `return p == 2;` would do it. — rossum, Dec 11 '16 at 22:22

score 2 · Accepted Answer · answered Dec 11 '16 at 19:35

If a number is not prime, then it has at least two factors: 63 = 7 x 9 or 121 = 11 x 11 for example. The smaller of the two factors has to be less than or equal to the square root of the original number. If you find any factor, then the number is not prime so you can stop searching once you have found the first factor.

By searching up to and including the square root you are guaranteed to find a factor of a composite number. If the search reaches past the square root without finding a factor, then the number must be prime with factors 1 and the number itself. There is no need to carry on searching beyond the square root as you will not learn anything new and will waste time.

Java Prime Checker

1 Answers1