Java 总理检查员

Question

如果在 java 中找到素数检查器，它使用此方法。 有人可以解释一下，为什么 for 循环会求出所搜索素数的平方根？ - 有没有更有效的方法来做到这一点？ - 谢谢！

    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;  
}

Answer 1

如果一个数不是素数，那么它至少有两个因数：例如 63 = 7 x 9 或 121 = 11 x 11。两个因数中较小的一个必须小于或等于原始数的平方根。如果找到任何因子，则该数字不是质数，因此一旦找到第一个因子就可以停止搜索。

通过搜索直到并包括平方根，您一定会找到合数的因数。如果搜索超过了平方根而没有找到一个因数，那么这个数必须是因数 1 和这个数本身的素数。没有必要在平方根之外继续搜索，因为您不会学到任何新东西并且会浪费时间。