打印前n个素数的复杂度

Question

在面试中我被问到这个问题：

Write a function to print first n prime numbers

函数如下所示：

Live on ideone

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

  if (primes == n)
      break;
}

简单的复杂性分析可能导致 O(n√n)
但是面试官说outerloop不会直接去n因为比如要找到前100个质数我们需要循环到541（也就是第100个质数）

那么我们如何表达给定的时间复杂度？

Answer 1

回答这个问题需要高等数学，即素数的分布规律。它告诉你 (https://en.wikipedia.org/wiki/Prime_number_theorem) 第 n 个质数的值大约是 n.log(n).

那么你的复杂度是O(n√n.log(n)√log(n))。

---

我可能会发现这个界限是悲观的，因为并非所有迭代 运行 直到 √n。例如，立即检测到偶数。对于更严格的界限，您需要整数的最小因子的分布规律。