查找第n个素数

Question

我写了下面的代码来找出第n个质数。这可以在时间复杂度上得到改善吗？

描述：

ArrayList arr存储计算出的质数。一旦arr达到一个大小'n'，循环就会退出，我们将检索ArrayList中的第n个元素。在计算质数之前将数字2和3相加，并检查从4开始的每个数字是否为质数。

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

Answer 1

是。

你的算法产生了O(n^2)操作(也许我不准确，但看起来是这样)，其中n是结果。

对数O(ipn*((N)的对数算法有几种。您只能在其中创建inp步骤，并假设n = 2ipn*ln(ipn)。n应该大于ipn-prime。(我们知道素数http://en.wikipedia.org/wiki/Prime_number_theorem的分布)

无论如何，您可以改进现有的解决方案：

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

Answer 2

你可以做以下几件事来加快速度：

1. 在5处开始计数，并将其递增2而不是1，然后不检查循环中的mod 2。
2. 而不是从
3. /2处开始临时，而是在第一个
4. 处以2开始。

我不确定这是否可以提高复杂度，但(2)上面的将从O(n^2)减少到O(n*sqrt(n))

Answer 3

public static void Main()
    {
        Console.Write("Enter a Number : ");
        int num;
        int[] arr = new int[10000];
        num = Convert.ToInt32(Console.ReadLine());
        int k;
        k = 0;
        int t = 1;
        for (int j = 1; j < 10000; j++)
        {
            for (int i = 1; i <= j; i++)
            {
                if (j % i == 0)
                {
                    k++;
                }
            }
            if (k == 2)
            {
                arr[t] = j;
                t++;
                k = 0; 
            }
            else
            { 
                k = 0;
            } 
        }
        Console.WriteLine("Nth Prime number. {0}", arr[num]);
        Console.ReadLine();
    }