Какую асимптотику имеет следующий код:
C++ |
Python |
#include <iostream>
using namespace std;
int main()
{
int cnt = 0, n;
cin >> n;
for (int i = 2; i <= n; ++i)
{
for (int j = 2; j * j <= i; ++j)
{
if (n % j == 0)
{
++cnt;
}
}
}
cout << cnt << endl;
return 0;
}
|
cnt = 0
n = int(input())
for i in range( 2, n + 1 ):
for j in range(2, int(i**0.5) + 1):
if n % j == 0:
cnt += 1
print(cnt)
|
Ответ выведите в виде математической формулы, без O.
Степень указывайте значком
**
, умножение знаком
*
, корень квадратный -
sqrt()
, логарифм -
log2(n)
. Пробелы в формуле не ставьте.