3

我在下面编写了以下代码来查找第 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));
    }
}
4

4 回答 4

10

是的。

您的算法进行O(n^2)操作(也许我不准确,但似乎如此),其中n是结果。

有采用O(ipn* log(log(n)))的http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes算法。您只能在其中进行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));
    }
}
于 2013-02-07T02:48:25.140 回答
2

您可以做一些事情来加快速度:

  1. 从 5 开始计数器并将其增加 2 而不是 1,然后不要在循环中检查 mod 2。
  2. 不是从 counter / 2 开始 temp,而是从第一个奇数 <= int(sqrt(counter)) 开始
  3. 将温度减 2。

我不确定它是否算作提高复杂性,但上面的 (2) 将从 O(n^2) 变为 O(n*sqrt(n))

于 2013-02-07T02:47:03.753 回答
0
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();
    }
于 2019-01-15T13:56:56.900 回答
0
    System.out.println("Enter The number n: ");
    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();

    int x = 0;
    String prime = "";

    for (int i = 1; i <= n; i++) {

        int counter = 0;

        for (x = i; x >= 1; x--) {

            if (i % x == 0) {
                counter++;
            }
        }

        if (counter == 2){
            prime =  prime + i + " ";
        }

    }

    System.out.println(prime);
}

}

于 2021-10-24T16:25:48.847 回答