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

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) 时间。