Временная сложность алгоритма, который находит простые числа по заданному вектору

Question

Я пытаюсь найти временную сложность следующего алгоритма, который находит простые числа по данному вектору. В частности, я не уверен насчет последнего цикла 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

Работа, выполненная с помощью базового сита Erastophene , почти полностью отбирает составные числа и занимает

В вашем случае вы начинаете с i * i, что эффективно уменьшает количество операций выбраковки на i - 1 для каждого простого числа. Итак, нам нужно посчитать количество всех простых чисел до n (vsize). Это

Итак, асимптотически имеем

Где последним добавлением является число простых чисел, меньших n.