Java:递归地找出一个数字是否为质数

Question

我正在编写一个函数，如果数字是质数则返回 true，否则返回 false

这是我当前的代码:

    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”这样的数字，我会遇到内存不足错误。我如何调整此代码以在空间方面更高效？

Answer 1

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

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

但是，值得指出的是，一些数学递归问题的计算解决方案迭代远比朴素递归好得多。主要(哈!)的例子是斐波那契数列。对于大 n，简单的递归解决方案会消耗内存并执行冗余计算，而迭代解决方案则更快更好。