找到第n个素数 [英] find nth prime number

问题描述

我已经写了下面的下面的code，找到第n个素数。可以在时间复杂度这得到改善呢？

说明：

改编将计算质数的ArrayList。一旦ARR达到大小N，该LOPP出口和我们取得ArrayList中第n个元素。数字2和3中加入的素数计算之前，每个数从4开始被检查为素数或不

 公共无效calcPrime（INT INP）{
    ArrayList的＆LT;整数GT; ARR =新的ArrayList＆LT;整数GT;（）; //商店素数
                                                      //计算到目前为止
    //添加素数2和3，主阵列改编
    arr.add（2）;
    arr.add（3）;

    //检查数量为4首要出发
    INT计数器= 4;
     //检查是否改编的规模已经达到INP这是'N'，如果是终止while循环
    而（arr.size（）＆LT; = INP）{
        //不检查素数是否是能被2整除
        如果（计数器％2！= 0）{
            //检查当前一些'反'是完全分割
           //计数器/ 2〜3
            INT TEMP =计数器/ 2;
            而（温度＆GT; = 3）{
                如果（计数器％temp == 0）
                    打破;
                温度 - ;
            }
            如果（温度＆其中; = 3）{
                arr.add（柜）;
            }
        }
        反++;
    }

    的System.out.println（完成+ arr.get（INP））;
    }
}
 

解决方案

是

您算法生成为O（n ^ 2）操作（也许我并不准确，但似乎如此）， 其中<强> N 的结果。

有<一href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes算法，需要 O（IPN *日志（的log（n）））。您可以在只 INP 的步骤，并假设 N = 2ipn * LN（IPN）。 N 只是应大于 IPN -prime。 （我们知道素数的分布<一href="http://en.wikipedia.org/wiki/Prime_number_theorem">http://en.wikipedia.org/wiki/Prime_number_theorem)

无论如何，你可以提高现有的解决方案：

 公共无效calcPrime（INT INP）{
    ArrayList的＆LT;整数GT; ARR =新的ArrayList＆LT;整数GT;（）;
    arr.add（2）;
    arr.add（3）;

    INT计数器= 4;

    而（arr.size（）＆LT; INP）{
        如果（计数器％2 = 0＆放大器;！＆安培;！专柜％3 = 0）{
            INT TEMP = 4;
            而（温度*温度＆LT; =计数器）{
                如果（计数器％temp == 0）
                    打破;
                临时++;
            }
            如果（临时*温度＆GT;计数器）{
                arr.add（柜）;
            }
        }
        反++;
    }

    的System.out.println（完成+ arr.get（INP-1））;
    }
}
 

I've written the following code below to find the nth prime number. Can this be improved in time complexity?

Description:

The ArrayList arr stores the computed prime numbers. Once arr reaches a size 'n', the lopp exits and we retrieve the nth element in the arraylist. Numbers 2 and 3 are added before the prime numbers are calculated, and each number starting from 4 is checked to be prime or not.

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>(); // stores prime numbers 
                                                      // calculated so far
    // add prime numbers 2 and 3 to prime array 'arr'
    arr.add(2); 
    arr.add(3);

    // check if number is prime starting from 4
    int counter = 4;
     // check if arr's size has reached inp which is 'n', if so terminate while loop
    while(arr.size() <= inp) {
        // dont check for prime if number is divisible by 2
        if(counter % 2 != 0) {
            // check if current number 'counter' is perfectly divisible from 
           // counter/2 to 3
            int temp = counter/2;
            while(temp >=3) {
                if(counter % temp == 0)
                    break;
                temp --;
            }
            if(temp <= 3) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp));
    }
}

解决方案

Yes.

Your algorithm make O(n^2) operations (maybe I'm not accurate, but seems so), where n is result.

There are http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes algorithm that takes O(ipn* log(log(n))). You can make only inp steps in it, and assume that n = 2ipn*ln(ipn). n just should be greater then ipn-prime. (we know distributions of prime numbers http://en.wikipedia.org/wiki/Prime_number_theorem)

Anyway, you can improve existing solution:

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    arr.add(2);
    arr.add(3);

    int counter = 4;

    while(arr.size() < inp) {
        if(counter % 2 != 0 && counter%3 != 0) {
            int temp = 4;
            while(temp*temp <= counter) {
                if(counter % temp == 0)
                    break;
                temp ++;
            }
            if(temp*temp > counter) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp-1));
    }
}

这篇关于找到第n个素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！