Гид по технологиям

Как посчитать количество точных квадратов между двумя числами

• 4 min read • Программирование • Обновлено 04 Dec 2025
Количество квадратов между двумя числами
Количество квадратов между двумя числами

Графика: концепция квадратов и кубов на фоне языков программирования Python, JavaScript, C++

Задача

Даны два числа num1 и num2. Нужно найти, сколько целых чисел в диапазоне [num1, num2] являются точными квадратами (то есть равны k*k для некоторого целого k).

Определение: точный квадрат — целое число, равное квадрату целого числа.

Примеры

  • Пример 1: num1 = 10, num2 = 100. Квадраты: 16, 25, 36, 49, 64, 81, 100 → ответ 7.
  • Пример 2: num1 = 15, num2 = 82. Квадраты: 16, 25, 36, 49, 64, 81 → ответ 6.
  • Пример 3: num1 = 3, num2 = 36. Квадраты: 4, 9, 16, 25, 36 → ответ 5.

Important: формула корректна при num1 ≤ num2 и для неотрицательных аргументов. При работе с отрицательными числами учтите, что отрицательные целые не дают положительных точных квадратов.

Наивный подход (простая проверка каждого числа)

Идея: для каждого i от num1 до num2 проверяем, существует ли целое j такое, что j*j == i. Это простой и очевидный способ, но он медленнее при большом диапазоне.

C++ (наивный)

// C++ program to count the total number of
// perfect squares between 2 numbers
#include 
using namespace std;

int countTotalSquares(int num1, int num2)
{
    int result = 0;
    for(int i=num1; i<=num2; i++)
    {
        for(int j=1; j*j<=i; j++)
        {
            if(j*j == i)
            {
                result++;
            }
        }
    }
    return result;
}

int main()
{
    int num1 = 10;
    int num2 = 100;
    cout << "Total number of perfect squares between " << num1 << " and " << num2 << ": " << countTotalSquares(num1, num2) << endl;

    int num3 = 15;
    int num4 = 82;
    cout << "Total number of perfect squares between " << num3 << " and " << num4 << ": " << countTotalSquares(num3, num4) << endl;

    int num5 = 3;
    int num6 = 36;
    cout << "Total number of perfect squares between " << num5 << " and " << num6 << ": " << countTotalSquares(num5, num6) << endl;

    int num7 = 12;
    int num8 = 65;
    cout << "Total number of perfect squares between " << num7 << " and " << num8 << ": " << countTotalSquares(num7, num8) << endl;

    return 0;
}

Ожидаемый вывод:

Total number of perfect squares between 10 and 100: 7
Total number of perfect squares between 15 and 82: 6
Total number of perfect squares between 3 and 36: 5
Total number of perfect squares between 12 and 65: 5

Python (наивный)

# Python program to count the total number of
# perfect squares between 2 numbers

def countTotalSquares(num1, num2):
    result = 0
    for i in range(num1, num2+1):
        j = 1
        while j * j <= i:
            if j * j == i:
                result = result + 1
            j = j + 1
    return result

num1 = 10
num2 = 100
print("Total number of perfect squares between", num1, "and", num2, ":", countTotalSquares(num1, num2))

num3 = 15
num4 = 82
print("Total number of perfect squares between", num3, "and", num4, ":", countTotalSquares(num3, num4))

num5 = 3
num6 = 36
print("Total number of perfect squares between", num5, "and", num6, ":", countTotalSquares(num5, num6))

num7 = 12
num8 = 65
print("Total number of perfect squares between", num7, "and", num8, ":", countTotalSquares(num7, num8))

Ожидаемый вывод:

Total number of perfect squares between 10 and 100: 7
Total number of perfect squares between 15 and 82: 6
Total number of perfect squares between 3 and 36: 5
Total number of perfect squares between 12 and 65: 5

JavaScript (наивный)

// JavaScript program to count the total number of
// perfect squares between 2 numbers

function countTotalSquares(num1, num2) {
    var result = 0;
    for(let i=num1; i<=num2; i++) {
        for(let j=1; j*j<=i; j++) {
            if(j*j == i) {
                result++;
            }
        }
    }
    return result;
}

var num1 = 10;
var num2 = 100;
document.write("Total number of perfect squares between " + num1 + " and " + num2 + ": " + countTotalSquares(num1, num2) + "\n");

var num3 = 15;
var num4 = 82;
document.write("Total number of perfect squares between " + num3 + " and " + num4 + ": " + countTotalSquares(num3, num4) + "\n");

var num5 = 3;
var num6 = 36;
document.write("Total number of perfect squares between " + num5 + " and " + num6 + ": " + countTotalSquares(num5, num6) + "\n");

var num7 = 12;
var num8 = 65;
document.write("Total number of perfect squares between " + num7 + " and " + num8 + ": " + countTotalSquares(num7, num8) + "\n");

Ожидаемый вывод:

Total number of perfect squares between 10 and 100: 7
Total number of perfect squares between 15 and 82: 6
Total number of perfect squares between 3 and 36: 5
Total number of perfect squares between 12 and 65: 5

Эффективный подход (формула)

Наблюдение: все точные квадраты равны k^2. Если k пробегает целые значения, то квадраты на оси чисел идут подряд: 1, 4, 9, 16, … Чтобы посчитать, сколько квадратов лежит в [num1, num2], достаточно найти количество целых k таких, что k^2 ∈ [num1, num2]. Это равносильно найти целые k в диапазоне [ceil(sqrt(num1)), floor(sqrt(num2))].

Формула:

Total = floor(sqrt(num2)) - ceil(sqrt(num1)) + 1

Сложность: вычисление квадратных корней и округлений — O(1) (в терминах арифметики); асимптотика ≈ O(1) по времени (на практике затратная операция — sqrt), заметно быстрее на больших интервалах по сравнению с наивным методом.

Note: для отрицательных num2 все квадратные числа ≤ num2 отсутствуют, результат равен 0.

Важные крайние случаи и ограничения

  • Если num1 > num2 — интерпретируйте как пустой интервал → результат 0.
  • При больших числах с плавающей арифметикой возможны проблемы точности (редкие ошибки округления возле границ). Решение — работать с целыми операциями: найти r = floor(sqrt(num2)), проверить r*r > num2 → корректировать, аналогично для l = ceil(sqrt(num1)).
  • Нулевая граница: 0 = 0*0 считается точным квадратом; включается, если num1 ≤ 0 ≤ num2.

Реализации с формулой (эффективные)

C++ (эффективно)

// C++ program to count the total number of
// perfect squares between 2 numbers
#include 
using namespace std;

int countTotalSquares(int num1, int num2)
{
    if (num1 > num2) return 0;
    int l = (int)ceil(sqrt(max(0, num1))); // защитная проверка для отрицательных
    int r = (int)floor(sqrt(max(0, num2)));
    if (r < l) return 0;
    return (r - l + 1);
}

int main()
{
    int num1 = 10;
    int num2 = 100;
    cout << "Total number of perfect squares between " << num1 << " and " << num2 << ": " << countTotalSquares(num1, num2) << endl;

    int num3 = 15;
    int num4 = 82;
    cout << "Total number of perfect squares between " << num3 << " and " << num4 << ": " << countTotalSquares(num3, num4) << endl;

    int num5 = 3;
    int num6 = 36;
    cout << "Total number of perfect squares between " << num5 << " and " << num6 << ": " << countTotalSquares(num5, num6) << endl;

    int num7 = 12;
    int num8 = 65;
    cout << "Total number of perfect squares between " << num7 << " and " << num8 << ": " << countTotalSquares(num7, num8) << endl;

    return 0;
}

Python (эффективно)

# Python program to count the total number of
# perfect squares between 2 numbers
import math

def countTotalSquares(num1, num2):
    if num1 > num2:
        return 0
    l = math.ceil(math.sqrt(max(0, num1)))
    r = math.floor(math.sqrt(max(0, num2)))
    if r < l:
        return 0
    return r - l + 1

num1 = 10
num2 = 100
print("Total number of perfect squares between", num1, "and", num2, ":", countTotalSquares(num1, num2))

num3 = 15
num4 = 82
print("Total number of perfect squares between", num3, "and", num4, ":", countTotalSquares(num3, num4))

num5 = 3
num6 = 36
print("Total number of perfect squares between", num5, "and", num6, ":", countTotalSquares(num5, num6))

num7 = 12
num8 = 65
print("Total number of perfect squares between", num7, "and", num8, ":", countTotalSquares(num7, num8))

JavaScript (эффективно)

// JavaScript program to count the total number of
// perfect squares between 2 numbers

function countTotalSquares(num1, num2) {
    if (num1 > num2) return 0;
    const l = Math.ceil(Math.sqrt(Math.max(0, num1)));
    const r = Math.floor(Math.sqrt(Math.max(0, num2)));
    if (r < l) return 0;
    return r - l + 1;
}

var num1 = 10;
var num2 = 100;
document.write("Total number of perfect squares between " + num1 + " and " + num2 + ": " + countTotalSquares(num1, num2) + "\n");

var num3 = 15;
var num4 = 82;
document.write("Total number of perfect squares between " + num3 + " and " + num4 + ": " + countTotalSquares(num3, num4) + "\n");

var num5 = 3;
var num6 = 36;
document.write("Total number of perfect squares between " + num5 + " and " + num6 + ": " + countTotalSquares(num5, num6) + "\n");

var num7 = 12;
var num8 = 65;
document.write("Total number of perfect squares between " + num7 + " and " + num8 + ": " + countTotalSquares(num7, num8) + "\n");

Дополнительные подходы и эвристики

  • Итерировать k (корни), а не i (числа): вычислить k от ceil(sqrt(num1)) до floor(sqrt(num2)) и по каждому k генерировать k*k; это полезно, если нужно не только посчитать, но и перечислить квадраты.
  • Для больших целых (bignum) избегайте плавающих sqrt: можно выполнять бинарный поиск целого r такое, что rr ≤ num2 < (r+1)(r+1).
  • Если требуется производительность в потоковой обработке, поддерживайте текущие k и увеличивайте до тех пор, пока k*k ≤ текущий правый предел.

Когда формула может «подвести» (крайние случаи)

  • Потеря точности float/double при очень больших аргументах: используйте целочисленные методы (binary search) для sqrt.
  • Интервалы, содержащие отрицательные числа: квадраты сами по себе неотрицательные, поэтому диапазоны полностью в отрицательной части дают 0.

Набор тестов (примеры для проверки)

  • (10, 100) → 7
  • (15, 82) → 6
  • (3, 36) → 5
  • (0, 0) → 1 (0 считается квадратом)
  • (-10, -1) → 0
  • (1, 1) → 1
  • (2, 3) → 0
  • (Integer.MAX-1, Integer.MAX) — проверка на переполнение и точность

Чек-лист для роли

  • Студент: убедитесь, что понимаете определение точного квадрата; напишите наивную реализацию.
  • Интервьюируемый: сначала объясните формулу, потом предложите наивный вариант для полноты.
  • Backend-разработчик: выберите бинарный integer-sqrt для больших значений, избегайте double-погрешностей.

Краткое резюме

  • Самая быстрая практическая формула: floor(sqrt(num2)) − ceil(sqrt(num1)) + 1.
  • Наивный метод корректен, но медленнее для больших интервалов.
  • Проверяйте крайние случаи: num1 > num2, отрицательные диапазоны, проблемы точности при больших числах.

Код и примеры выше можно использовать как шаблон. Удачи в практических задачах и собеседованиях!

Поделиться: X/Twitter Facebook LinkedIn Telegram
Автор
Редакция

Похожие материалы

Виджет Google Tasks на Android — быстрый гайд
Android.

Виджет Google Tasks на Android — быстрый гайд

Запуск Sticky Notes при включении Windows 11
Windows 11

Запуск Sticky Notes при включении Windows 11

Как исправить WDF_Violation в Windows
Windows

Как исправить WDF_Violation в Windows

Добавить Windows 11 в меню GRUB
Загрузчик

Добавить Windows 11 в меню GRUB

Удаление колонтитулов в Word — быстрое руководство
Microsoft Word

Удаление колонтитулов в Word — быстрое руководство

Ярлык «Свойства системы» в Windows 11
Windows

Ярлык «Свойства системы» в Windows 11