Эффективно вычислять все идеальные квадратные числа для очень больших чисел, таких как 10 ** 20

Question

Примерами идеальных квадратных чисел являются 1,4,9,16,25 ....

Как вычислить все идеальные квадратные числа для очень больших чисел, таких как 10 pow 20. Для 10 Pow 20 есть 10 Pow 10 идеальных квадратных чисел.

Пока что я сделал ....

Bruteforce: вычислите x ** 2 в диапазоне от 1 до 10 Pow 10. Поскольку моя система принимает только 10 Pow 6. Это не т работа.

Подход с двумя указателями: я взял верхнюю и нижнюю границы ....

Верхняя граница равна 10 pow 20

Нижняя граница равна 1

Теперь я взял два указателя, один в начале, а другой в конце. Тогда следующий идеальный квадрат для нижней границы будет

нижняя граница + (sqrt (нижняя граница) * 2 + 1)

Пример: для 4 следующий идеальный квадрат равен

4 + (sqrt (4) * 2 + 1) = 9

Таким же образом верхняя граница будет уменьшаться

верхняя граница - (sqrt (верхняя граница) * 2-1)

Пример: для 25 предыдущий идеальный квадрат равен

25 - (sqrt (25) * 2-1) = 16

Оба вышеупомянутых подхода не сработали потому что верхняя граница очень очень большая число 10 Pow 20.

Как мы можем эффективно вычислить все идеальные квадраты до 10 Pow 20 за меньшее время?

Answer 1

Легко заметить разницу между идеальными квадратами:

0   1   4   9   16   25   ...
|___|___|___|___|_____|
  |   |   |   |    |
  1   3   5   7    9

Итак, у нас есть:

answer = 0;
for(i = 1; answer <= 10^20; i = i + 2)
    answer = answer + i;
    print(answer);
}

Поскольку вы хотите, чтобы все идеальные квадраты были до x, сложность по времени будет O (sqrt (x)), который может быть медленным при x = 10 ^ 20, чей квадрат равен 10 ^ 10.