这种寻找 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²)（因此是 Θ(n²)），因此如上所述，素数需要 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)) 个素数。

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

What would be the time complexity for this naive method finding n prime numbers?

ruby

algorithm

big-o

primes

time-complexity