查找第n个质数

Question

查找第n个质数

javaperformancealgorithmcomplexity-theoryprimes

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

- codewarrior

1

请为我们的程序提供一个直观的描述，或者至少提供注释。仅仅给我们一段代码并要求我们分析它会让任何人都难以理解它的含义。 - templatetypedef

可能有人会质疑它是否改善了计算复杂性，但是厄拉多塞筛法无论如何都要快得多。 - Jerry Coffin

@templatetypedef：在代码中添加了注释。 - codewarrior

完整答案请参考 https://dev59.com/82kw5IYBdhLWcg3wzd3Z#9704912。 - Will Ness

此外，首先在 Stack Overflow 上进行搜索是一个好习惯：http://stackoverflow.com/tags/primes/hot?filter=year。 - Will Ness

4个回答

2

以下是一些可以加速它的方法：

将计数器从5开始，并将其递增2而不是1，然后在循环中不检查mod 2。
将temp从counter / 2开始改为从第一个奇数开始 <= int(sqrt(counter))
将temp减少2。

我不确定它是否算作改进复杂度，但上述（2）将从O(n^2)变为O(n*sqrt(n))

- xpda

通过 temp 从 sqrt 开始的测试非常低效。我怀疑它甚至会使复杂度变得更糟。 - Will Ness

它的确如此。我没有详细分析过，但是那些半素数中更大因子至少是较小因子的四倍的单独增加了一个“log log n”因子。虽然我期望长期的常数因素减速会更糟糕。 - Daniel Fischer

@Daniel 根据实验结果，ideone.com/iNxOrC 中的倒数计数代码似乎以 m^1.5 的速度运行，其中 m 是顶限。对于顶限在 100k 到 1.2mln 范围内，实际运行时间的比率为 2.6x ... 3.6x，并且越来越糟糕。倒数计数代码中的 m^1.5 实际上是有意义的 - 没有提前截断，因此就好像通过所有小于 sqrt 的奇数测试 每个奇数。而在正向计数中，非质数奇数的成本最多与质数相同（如 M. O'Neill 所示），给出了 m^1.5/log(m)。 - Will Ness

@Will，“early cut-off”是什么意思？您会一直除下去，直到找到第一个因子或达到限制，无论您是向上还是向下计数，在这方面，两种方法都很相似。不过，如果向下计数，通常需要更长的时间才能找到第一个因子。我认为平均情况下应该是Θ(√n)（因此经验公式m^1.5适用），但我没有看到证明它的简单方法（最接近√n的因子比最小质因子更难把握）。 - Daniel Fischer

@Daniel，这就是我想说的，是的，更长的方式几乎是“一路走到黑”。当然，它在任何方面都不严谨。尝试找到在范围2..n内随机选择的合数的最大因子的“期望值”，类似于这样的东西（平均而言，这将是我们的截止点，向下计数）。n或sqrt(n)，我预计不会有太大的区别。 - Will Ness

@Daniel 哎呀，我好笨啊。当然它必须是i的平方根以下最大因子，对于i<-[2..n]。 - Will Ness

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

}

- Youssef

1

目前你的回答不够清晰。请编辑并添加更多细节，以帮助其他人理解它如何回答所提出的问题。你可以在帮助中心找到有关如何撰写好答案的更多信息。 - Community

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

- Deepanshu Rathore

1

你能否包含一些改进的指示？ - belwood

这个 [通过试除法计算质数，找到第n个质数] 是如何 [改进] 时间复杂度 的呢？ - greybeard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- xvorsx · Accepted Answer

是的。

你的算法执行了O(n^2)次操作（可能我不太准确，但似乎是这样），其中n是结果。

有一种埃拉托斯特尼筛法算法，它只需要O(ipn* log(log(n)))的时间复杂度。在此算法中，您可以执行仅inp步，并假设n = 2ipn*ln(ipn)。 n只需大于ipn素数即可。（我们知道素数的分布情况，详见素数定理）

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

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