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

Иллюстрация: квадрат и куб — Python, JavaScript, C++

Важно: результаты определяются для целых неотрицательных чисел. Если диапазон включает отрицательные числа, они не содержат положительных полных квадратов (0 включается только если он в диапазоне).

Условие задачи

Даны два целых числа num1 и num2. Нужно найти общее количество полных квадратов (k^2, где k — целое) в диапазоне от num1 до num2 включительно.

Примеры:

num1 = 10, num2 = 100 → полные квадраты: 16, 25, 36, 49, 64, 81, 100 → результат 7.
num1 = 15, num2 = 82 → полные квадраты: 16, 25, 36, 49, 64, 81 → результат 6.
num1 = 3, num2 = 36 → полные квадраты: 4, 9, 16, 25, 36 → результат 5.

Простая (интуитивная) реализация

Идея: для каждого числа i в диапазоне проверить, является ли оно квадратом, перебирая возможные корни j (1..sqrt(i)). Это работает, но медленно при больших диапазонах.

Программа на C++ (наивная)

// Программа на C++ для подсчёта полных квадратов между двумя числами (наивный подход)
#include 
using namespace std;

int countTotalSquares(int num1, int num2)
{
    int result = 0;
    for(int i = num1; i <= num2; ++i)
    {
        if (i < 0) continue; // отрицательные числа не являются квадратами целого
        for(int j = 1; j*j <= i; ++j)
        {
            if(j*j == i)
            {
                result++;
                break; // мы нашли квадрат для i — можно перейти к следующему i
            }
        }
    }
    return result;
}

int main()
{
    int num1 = 10;
    int num2 = 100;
    cout << "Количество полных квадратов между " << num1 << " и " << num2 << ": " << countTotalSquares(num1, num2) << endl;

    int num3 = 15;
    int num4 = 82;
    cout << "Количество полных квадратов между " << num3 << " и " << num4 << ": " << countTotalSquares(num3, num4) << endl;

    int num5 = 3;
    int num6 = 36;
    cout << "Количество полных квадратов между " << num5 << " и " << num6 << ": " << countTotalSquares(num5, num6) << endl;

    int num7 = 12;
    int num8 = 65;
    cout << "Количество полных квадратов между " << num7 << " и " << num8 << ": " << countTotalSquares(num7, num8) << endl;

    return 0;
}

Python (наивный)

# Python: наивный подход
def count_total_squares(num1, num2):
    result = 0
    for i in range(num1, num2 + 1):
        if i < 0:
            continue
        j = 1
        while j * j <= i:
            if j * j == i:
                result += 1
                break
            j += 1
    return result

num1 = 10
num2 = 100
print("Количество полных квадратов между", num1, "и", num2, ":", count_total_squares(num1, num2))

JavaScript (наивный)

// JavaScript: наивный подход
function countTotalSquares(num1, num2) {
    var result = 0;
    for (let i = num1; i <= num2; i++) {
        if (i < 0) continue;
        for (let j = 1; j * j <= i; j++) {
            if (j * j === i) {
                result++;
                break;
            }
        }
    }
    return result;
}

console.log("Количество полных квадратов между 10 и 100:", countTotalSquares(10, 100));

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

Наблюдение: целые полные квадраты в диапазоне [num1, num2] — это квадраты целых корней k, где k от ceil(sqrt(num1)) до floor(sqrt(num2)). Поэтому формула:

количество = floor(sqrt(num2)) - ceil(sqrt(num1)) + 1

Формула работает за O(1) (время вычисления корней), вместо O((num2-num1)*sqrt(num2)).

Примечание: при num1 > num2 результат должен быть 0. Также если num2 < 0 — 0 (нет положительных квадратов). При num1 <= 0 <= num2 нужно правильно учесть 0 (0 = 0^2).

Программа на C++ (эффективно)

// C++: эффективный подход
#include 
using namespace std;

int countTotalSquares(int num1, int num2)
{
    if (num2 < 0 || num1 > num2) return 0;
    // ограничиваем снизу нулём — отрицательные значения не влияют
    int low = max(num1, 0);
    int high = num2;
    int a = (int)ceil(sqrt((double)low));
    int b = (int)floor(sqrt((double)high));
    int res = b - a + 1;
    return max(0, res);
}

int main() {
    cout << "Количество полных квадратов между 10 и 100: " << countTotalSquares(10, 100) << endl;
    cout << "Количество полных квадратов между 15 и 82: " << countTotalSquares(15, 82) << endl;
    cout << "Количество полных квадратов между 3 и 36: " << countTotalSquares(3, 36) << endl;
    cout << "Количество полных квадратов между 12 и 65: " << countTotalSquares(12, 65) << endl;
    return 0;
}

Python (эффективно, с импортом)

import math

def count_total_squares(num1, num2):
    if num2 < 0 or num1 > num2:
        return 0
    low = max(num1, 0)
    high = num2
    a = math.ceil(math.sqrt(low))
    b = math.floor(math.sqrt(high))
    return max(0, b - a + 1)

print("Количество полных квадратов между 10 и 100:", count_total_squares(10, 100))

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

function countTotalSquares(num1, num2) {
    if (num2 < 0 || num1 > num2) return 0;
    const low = Math.max(num1, 0);
    const high = num2;
    const a = Math.ceil(Math.sqrt(low));
    const b = Math.floor(Math.sqrt(high));
    return Math.max(0, b - a + 1);
}

console.log("Количество полных квадратов между 10 и 100:", countTotalSquares(10, 100));

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

Погрешности плавающей точки: при очень больших числах sqrt(double) может дать неточную дробную часть. Для критичных задач используйте целочисленные методы (например, бинарный поиск целого корня).
Отрицательные границы: не забывайте, что отрицательные числа не дают положительных полных квадратов.
Если num1 > num2 — возвращайте 0.

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

Целочисленный integer sqrt: реализуйте функцию integer_sqrt(n) через бинарный поиск, чтобы полностью избежать погрешностей double.
Для потоковых данных или живого счётчика (где диапазон постоянно сдвигается) можно хранить k и обновлять счёт.

Быстрая шпаргалка (Cheat sheet)

Формула: floor(sqrt(num2)) - ceil(sqrt(num1)) + 1
Временная сложность: O(1) (для одного вычисления корня)
Память: O(1)
Учитывайте: отрицательные числа, num1>num2, точность sqrt

Факт-бокс: ключевые числа

Наивный перебор: O((num2-num1) * sqrt(num2)) операций в худшем случае.
Формула с корнями: O(1) арифметических операций (с учётом стоимости sqrt).

Критерии приёмки (тесты)

Вход: num1=10, num2=100 → ожидаемый результат 7.
Вход: num1=15, num2=82 → ожидаемый результат 6.
Вход: num1=3, num2=36 → ожидаемый результат 5.
Вход: num1=-10, num2=0 → ожидаемый результат 1 (0 это 0^2).
Вход: num1=5, num2=4 → ожидаемый результат 0 (инвертированный диапазон).
Очень большие значения: num1=1, num2=10^12 — функция должна корректно вернуть целое число; при необходимости используйте integer sqrt.

Роль — чеклист для разработчика

Проверить граничные значения (отрицательные, ноль, num1>num2).
Выбрать реализацию: формула (скорость) или integer-sqrt (точность).
Добавить модульные тесты по «Критериям приёмки».
Документировать поведение при чрезвычайных входных данных.

Короткое объявление (100–200 слов)

Ищете простой способ посчитать, сколько полных квадратов лежит между двумя числами? Самый быстрый метод — использовать корни: количество равняется floor(sqrt(num2)) - ceil(sqrt(num1)) + 1. Это решение компактно, быстро и подходит для больших диапазонов, но требует учёта краёв: отрицательных чисел, ситуации num1>num2 и возможных погрешностей при вычислении sqrt для очень больших чисел. Для абсолютной точности используйте целочисленную функцию вычисления квадратного корня (binary search). В статье приведены рабочие примеры на C++, Python и JavaScript — как наивные, так и оптимизированные версии, а также набор тестов и рекомендации по выбору реализации.

Итог

Используйте формулу с floor и ceil для быстрого ответа.
Если нужна абсолютная точность на больших числах — реализуйте integer sqrt.
Всегда тестируйте граничные случаи: отрицательные числа, 0 и перевёрнутые диапазоны.