这种寻找 n 个素数的朴素方法的时间复杂度是多少？

Question

class Primes
  def initialize
    @primes = []
  end

  def prime_iterative(n)
    i = 2
    while @primes.size < n do
      @primes << i if is_prime?(i)
      i += 1
    end
    @primes
  end
  
  def is_prime?(n)
    @primes.each { |prime| return false if n % prime == 0 }
    true
  end
end

primes = Primes. new
puts primes.prime_iterative 10

它发现 n 个素数并不是所有小于 n 的素数。我无法确定上限

Answer 1

所以这是素数的试除法，效率不如埃拉托色尼筛法。

它检查每对素数的可整性，所以肯定是 ?(n²)。

它也是 O(n² log n)，因为第 n 个素数是 (1 + o(1)) n log n，悲观地我们将每个数除以前 n 个素数中的每个数直到第 n 个素数。

我们可以通过观察每个复合 c 都有一个质因子 ? ?c，所以素数需要 O(n²) 时间，如上所述，复合只需要 O(n log n ?(n/log n)) 因为每个都有一个素数因子？O(?(n log n))，这意味着我们检查 O(?(n log n)/log ?(n log n)) = O(?(n/log n)) 素数。