java - 打印前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)
但是面试官说外层循环不会简单的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。例如，立即检测到偶数。对于更严格的界限，您需要整数的最小因子的分布规律。