面试问题：递归生成质数的最快方法是什么？

Question

质数的生成很简单，但是递归地找到它并生成（质数）的最快方法是什么？

这是我的解决方案。但是，这不是最佳方法。我认为是O（N * sqrt（N））。如果我错了，请纠正我。

    public static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        } else if (n % 2 == 0 & n != 2) {
            return false;
        } else {
            return isPrime(n, (int) Math.sqrt(n));
        }
    }

    private static boolean isPrime(int n, int i) {
        if (i < 2) {
            return true;
        } else if (n % i == 0) {
            return false;
        } else {
            return isPrime(n, --i);
        }
    }

   public static void generatePrimes(int n){
       if(n < 2) {
            return ;
       } else if(isPrime(n)) {
            System.out.println(n);
       }

       generatePrimes(--n);

   }

   public static void main(String[] args) {

        generatePrimes(200);
   }

Answer 1

对于递归，您应该使用 记忆
来改善递归功能，这意味着如果找到素数将其保存在数组中，并且在isPrime(n)未调用isPrime（n，（int）Math.sqrt（
n））。同样，如果isPrime（n，i）返回true，将其添加到素数列表中，则最好对数组进行排序以进行二进制搜索，在C＃中有一个排序列表，然后进行二进制搜索操作[使n个项目的列表取O（n
log n）并且搜索是O（log（n））]我不知道Java [但是您可以实现]。

编辑： 您当前的方法是，O(n sqrt(n))但按照我的要求，它可以按相同顺序排列！但是性能更好，实际上顺序是这样的，O(n sqrt(n) / log (n) + n log(n/log(n)))并且因为log（n）小于n^Epsilon，所以最好这样说，O(n sqrt(n))但是如您所见，它将以更快的速度运行log（n）。

同样最好是i-2不是i-并在启动时进行一些额外的检查以更快地运行算法2 * log（n）。