Java：递归判断一个数是否为素数

Question

我正在编写一个函数，returns如果一个数是素数则为真，否则为假

这是我当前的代码：

    public static boolean checkPrime(int n, int currDivisor){
        if(n < 2){
            return true;
        }
        if(currDivisor == (n/2)){
            return true;
        }
        else if(n % currDivisor == 0 ){
            return false;           
        }
        else{
            return checkPrime(n, currDivisor + 1);
        }
    }

    public static void main(String[] args){
        System.out.println(checkPrime(23352, 2));
    }

它适用于很多测试用例，除了像“1000000007”这样的数字，我会遇到内存不足错误。我如何调整此代码以提高 space 的效率？

Answer 1

根本问题是递归不是正确的方法。素数测试不是递归问题，对于大量数据，您总是会很快超出可用存储空间。我建议你在网上做一些关于 "primality testing".

的研究

关于判断一个问题是否递归的经验法则，我已经这样做了很长时间，我不确定我是否可以表达已经变得完全直观的东西，所以我会让别人来做.

但是，值得指出的是，一些数学上递归的问题具有计算解决方案，其中迭代远比朴素递归好得多。主要（哈！）的例子是斐波那契数列。对于大 n，简单的递归解决方案会占用内存并执行冗余计算，而迭代解决方案则更快更好。

Answer 2

我看到的第一个问题是您的程序存在错误。似乎认为 0、1 和 4 是素数而 3 不是。我看到的第二个问题是，它在递归之前没有正确处理简单情况，这是在浪费堆栈帧。这是我对您的代码的修改：

public static boolean checkPrime(int n) {
    return checkPrime1(n, 3);
}

public static boolean checkPrime1(int n, int currDivisor) {
    if (n < 2) {
        return false;
    }

    if (n % 2 == 0) {
        return (n == 2);
    }

    if (currDivisor * currDivisor > n) {
        return true;
    }

    if (n % currDivisor == 0) {
        return false;
    }

    return checkPrime1(n, currDivisor + 2);
}

就处理而言：

System.out.println(checkPrime(1000000007));

您仍然会得到 java.lang.WhosebugError，但这还没有结束。大多数语言都会决定为特定目的分配多少内存。像 Perl 这样罕见的语言会将内存重新分配给最需要它的任何资源，而不对程序的行为方式做出假设。

您可以更改分配给 Java 堆栈的内存量——使用 -Xss2m 参数调用 java 会分配足够的额外堆栈让您测试 1000000007 (true, 顺便说一下。)

如果将上面的三个 int 声明更改为 long，只要展开堆栈 (-Xss4m 在这种情况下。）

我并不是说这是递归的好问题，它不是。但是，如果您要使用递归，请明智地使用它。差劲的递归使递归名声不好。有低效的递归 Fibonnaci 算法（通常是双递归）和高效的（单递归）算法。递归代码通常最适合递归数据。

一些语言，还没有Java一致，可以将上面的代码优化为尾递归，并使其有效地迭代性能。

Answer 3

    /*by mostafa asem aljbali*/
    static boolean isPrime(int num, int i){

        if (num <= 2){
            return (num == 2) ? true : false;
        }
        if (num % i == 0){
            return false;
        }
        if (i * i > num){
            return true;
        }

        return isPrime(num , (i + 1));
    }
 public static void main(String[] args){
    System.out.println("Is Prime: "+ isPrime(7, 2));
}

Java：递归判断一个数是否为素数

Java: Find out if a number is prime recursively

java

recursion

primes