c++ - 次のコードの複雑さは何ですか？

Question

次のコードの複雑さは何ですか？

for (int i = 1; i * i <= n; i++)
{
   if (n%i == 0)
     //do anything
}

Answer 1

ループは √ n回実行され、毎回条件が満たされるiのは因数ですn— 後者は重要な条件であり、慎重に分析する必要があります。の素因数分解に依存しnます。たとえば、nが素数の場合、条件は に対して 1 回だけ真i == 1となり、二度と真になりません。