计算找到第一个 'n' 个素数的时间复杂度

Question

寻找第一个'n'个素数的算法是：

while (number <= n) {
  boolean isPrime = true; 
  for (int divisor = 2; divisor <= (int)(Math.sqrt(number)); divisor++) {
    if (number % divisor == 0) {
      isPrime = false;      
      break;
    }
  }
  if(isPrime) 
    System.out.print(number + " ");
}

本书 "Introduction to java programming" 计算此算法的大 O 为：

由于在 for 循环中需要 √i 步来检查数字 i 是否为素数，因此该算法需要 √2 + √3 + √4 + ... + √n 步来找到所有小于或等于 n.

的素数

观察到，

√2 + √3 + √4 + ... + √n <= n√n

因此，该算法的时间复杂度为O(n√n)。

阙：

1. 他说，"it takes √i steps in the for loop to check whether number i is prime".

你觉得应该是(√i-1)步吧

2.请解释一下

√2 + √3 + √4 + ... + √n <= n√n

（我知道如果你只是将 'n' 替换为随机数，则关系成立。我需要解释）

Answer 1

回答 2：

对于 0 < i <= n 我们有 i <= n，因此 √i <= √n，所以 √i 的总和对于 i 在 1 和 n 之间 <= √n 在 1 和 n 之间的总和其中√n + √n ... + √n, n次

Answer 2

复杂性方面，减 1 没有效果（这是一个非正式的介绍）。
（实际上是floor(√n) - 1。）
您有 n - 1 个术语。添加√n n - 1次：

√n + √n + √n + ... + √n = (n-1)√n <= n√n

又因为√2,√3,√4,...都小于√n,所以

√2 + √3 + √4 + ... + √n <= √n + √n + √n + ... + √n <= n√n

Answer 3

（注意这不是一个完整的答案，它只是添加到@molbdnilo 的答案）

考虑一下：

1 + 2 + 3 + ... + n = n * (n+1) / 2 --> 时间复杂度是 O(n*(n+1)/2) == O(n^2) 尽管 (n * (n+1) / 2) <= (n^2)

现在考虑上面@molbdnilo 解释的内容；

and since √2, √3, √4, ... are all less than √n, it follows that

√2 + √3 + √4 + ... + √n <= √n + √n + √n + ... + √n <= n√n

希望能解开疑惑

计算找到第一个 'n' 个素数的时间复杂度

Calculating time complexity for finding first 'n' prime numbers

algorithm

big-o

time-complexity

回答 2：