打印第 n 个素数的复杂度

Question

在一次采访中，我被问到了以下问题：

Write a function to print first n prime numbers

该函数如下所示：

住在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第 -th 个素数的值约为n.log(n).

那么你的复杂性是O(n?n.log(n)?log(n)).

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