c++ - 给定 vector 查找素数的算法的时间复杂度

Question

我试图找到以下算法的时间复杂度，该算法在给定 vector 的情况下找到素数。具体来说，我不确定最后一个 for 循环是否嵌套了另一个循环。我觉得是O(sqrt(n)/2)，然后里面的循环是O(n)？

void PrimeFind (std::vector<bool> &vec)
{
  int vsize = vec.size();
  size_t sqvsize = ceil(sqrt(vsize));

  std::fill(vec.begin(), vec.end(), true);
  vec[0] = false;
  vec[1] = false;

  for (int i = 4; i < vsize; i += 2)
  {
    vec[i] = false;
  }

  for (int i = 3; i < sqrtvsize; i += 2)
  {
    if (vec[i])
    {
      for (int j = i * i; j < vsize; j += i)
      {
        vec[j] = false;
      }
    }
  }
}

Answer 1

基本 sieve of Erastophene 执行的工作几乎完全剔除合数，它需要

在您的情况下，您从 i * i 开始，这有效地减少了每个素数 i - 1 的剔除操作数。因此，我们需要计算所有素数的个数，直到 n (vsize)。 This is

所以，渐近地我们有

最后一个加数是 number of primes less than n .