专访问题：什么是递归生成素数的最快方法？ [英] Interview question : What is the fastest way to generate prime number recursively?

问题描述

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

下面是我的解决办法。然而，这并不是最好的办法。我认为这是O（N * SQRT（N））。请纠正我，如果我错了。

 公共静态布尔isPrime（INT N）{
        如果（正2）{
            返回false;
        }否则如果（N％2 == 0安培;！N = 2）{
            返回false;
        } 其他 {
            返回isPrime（正，（int）的的Math.sqrt（正））;
        }
    }

    私有静态布尔isPrime（INT N，int i）以{
        如果（ⅰ2）{
            返回true;
        }否则如果（N％我== 0）{
            返回false;
        } 其他 {
            返回isPrime（N，--i）;
        }
    }

   公共静态无效generatePrimes（INT N）{
       如果（正2）{
            返回 ;
       }否则如果（isPrime（正））{
            的System.out.println（N）;
       }

       generatePrimes（ -  N）;

   }

   公共静态无效的主要（字串[] args）{

        generatePrimes（200）;
   }
 

解决方案

有关recurrsion，你应该使用 <强>记忆化 提高你的递归函数，如果在数组中寻找素数的保存这意味着，在调用 isPrime（N）第一次检查在阵列中存在的号码，如果不打电话isPrime（N，（INT）的Math.sqrt（N））。此外，如果isPrime（N，I）返回true，将其添加到黄金清单，最好你的数组排序做的二进制搜索，在C＃中有排序列表，和n项的二进制搜索功能[制作名单需要O（N日志n）和搜索O（日志（N））]我不知道有关Java [但你可以实现它。

编辑：您目前的做法是为O（n的sqrt（N））但我approch它可以在相同的顺序！但更好的表现，其实顺序是为O（n的sqrt（N）/日志（N）+ N的log（n /的log（n）））键，因为日志（ n）是小然后 N R个小量，最好是说这是为O（n的sqrt（N））但作为你可以看到它会运行日志（n）的时间快。

另外，最好不要I-2不是我 - 和启动一些额外的检查，（n）时间更快的运行算法2 *日志。

Generation of prime number is simple but what is the fastest way to find it and generate( prime numbers) it recursively ?

Here is my solution. However, it is not the best way. I think it is O(N*sqrt(N)). Please correct me, if I am wrong.

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

解决方案

For recurrsion, You should use memoization to improve your recursive function, means if you finding prime number save it in array, and in call to isPrime(n) first check the number exists in array if not call to isPrime(n, (int) Math.sqrt(n)). also if isPrime(n,i) returns true, add it to prime list, it's better your array be sorted to do binary search, in C# there is sorted list, and binary search operation [making list of n item takes O(n log n) and searching is O(log(n))] i didn't know about java [but you can implement it].

Edit: your current approach is O(n sqrt(n)) but with my approch it can be in same order! but better performance, in fact the order is O(n sqrt(n) / log (n) + n log(n/log(n))) and because log(n) is smaller then n^Epsilon, it's better to say it's O(n sqrt(n)) but as you can see it will run log(n) time faster.

Also it's better do i-2 not i-- and some extra check in startup to run algorithm 2*log(n) time faster.

这篇关于专访问题：什么是递归生成素数的最快方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！