在范围内打印素数的代码有多复杂？

Question

此代码根据用户的输入在start和end之间打印所有素数。

它有多复杂？是O(end * sqrt(n))吗？

/**
 * Print prime numbers between start and end inputs
 * Time-Complexity: O(end * sqrt(n))
 * Space-Complexity: O(1) only one value as input
 * @param start, end
 * @return
 */
public void printPrimeSeries(int start, int end) {
    for (int i = start; i < end; i++) {
        if (findPrimeOrNot(i)) {
            System.out.println("The value " + i + " is a prime number");
        }
    }
}

public boolean findPrimeOrNot(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter start number for prime:");
    int startInput = scanner.nextInt();

    System.out.println("Enter end number for prime:");
    int endInput = scanner.nextInt();

    PrimeNoSeries primeNoSeries = new PrimeNoSeries();
    primeNoSeries.printPrimeSeries(startInput, endInput);
}

Answer 1

一步一步地走，为了简洁起见，让我们将开始值称为m，结束为n

• printPrimeSeries方法与n - m
• For各元素在上述范围内呈线性相关，内环复杂度为sqrt(n) - 2。忽略常量是sqrt(n)

因此，复杂性似乎是O((n - m) * sqrt(n))。

Answer 2

总的复杂度是O(结束-开始)*sqrt(结束))。FYI:我给你看了另一种估计，它没有那么紧：

在O-表示法中，您感兴趣的是最坏的情况，因此我们可以假设start总是0。现在我们只需要end来进行分析。

方法printPrimeSeries只是O(end)，从0到end。该方法使用findPrimeOrNot从2迭代到Math.sqrt(n)，即O(sqrt(n))。n的最大值是end的值，因此我们可以为我们的目的调用复杂度O(sqrt(end))。两者结合为O(end) * O( sqrt(end))，这就是O(end sqrt(End))。

这个问题有一些有趣的细节，与素数的分布有关。你可以读到它，here。