Время работы программы и циклы for

Упражнения на $O$-шки и асимптотику.

Сколько работает программа? Доступ к памяти. Кеширование. Арифметика. Вызов функций. Примеры.

Сколько работают циклы for? Примеры. Решето Эратосфена.

Задачи:

1. Даны N натуральных чисел, найти кол-во различных (решение сортировкой, хеш-таблицей).

2. Решить в натуральных числах уравнение N = $x^2$ + $y^2$ (решение за $\sqrt{N}$ сложений/вычитаний).

3. Дано N, найти натуральные x, y, z: N = xyz, и величина 2(xy + yz + zx) минимальна (решение за $N^{2/3}$).

4. Даны N различных чисел от 1 до N, сколько существует треугольников с такими длинами сторон (решение за $N^2$).