Número de cuadrados perfectos entre dos números dados

Dados dos números dados a y b donde 1<=a<=b, encuentre el número de cuadrados perfectos entre a y b (a y b inclusive).
Ejemplos 
 

Input :  a = 3, b = 8
Output : 1
The only perfect square in given range is 4.

Input : a = 9, b = 25
Output : 3
The three perfect squares in given range are 9, 
16 and 25

Método 1 : un enfoque ingenuo es verificar todos los números entre a y b (incluidos a y b) y aumentar la cuenta en uno cada vez que encontramos un cuadrado perfecto.

A continuación se muestra la implementación de la idea anterior:  

// A Simple Method to count squares between a and b
#include <bits/stdc++.h>
using namespace std;
 
int countSquares(int a, int b)
{
    int cnt = 0; // Initialize result
 
    // Traverse through all numbers
    for (int i = a; i <= b; i++)
 
        // Check if current number 'i' is perfect
        // square
        for (int j = 1; j * j <= i; j++)
            if (j * j == i)
                cnt++;
 
    return cnt;
}
 
// Driver code
int main()
{
    int a = 9, b = 25;
    cout << "Count of squares is "
         << countSquares(a, b);
    return 0;
}

// Java program to count squares between a and b
class CountSquares {
 
    static int countSquares(int a, int b)
    {
        int cnt = 0; // Initialize result
 
        // Traverse through all numbers
        for (int i = a; i <= b; i++)
 
            // Check if current number 'i' is perfect
            // square
            for (int j = 1; j * j <= i; j++)
                if (j * j == i)
                    cnt++;
        return cnt;
    }
}
 
// Driver Code
public class PerfectSquares {
    public static void main(String[] args)
    {
        int a = 9, b = 25;
        CountSquares obj = new CountSquares();
        System.out.print("Count of squares is " + obj.countSquares(a, b));
    }
}

# Python program to count squares between a and b
 
def CountSquares(a, b):
 
    cnt = 0 # initialize result
 
    # Traverse through all numbers
    for i in range (a, b + 1):
        j = 1;
        while j * j <= i:
            if j * j == i:
                 cnt = cnt + 1
            j = j + 1
        i = i + 1
    return cnt
 
# Driver Code
a = 9
b = 25
print ("Count of squares is:", CountSquares(a, b))

// C# program to count squares
// between a and b
using System;
 
class GFG {
 
    // Function to count squares
    static int countSquares(int a, int b)
    {
        // Initialize result
        int cnt = 0;
 
        // Traverse through all numbers
        for (int i = a; i <= b; i++)
 
            // Check if current number
            // 'i' is perfect square
            for (int j = 1; j * j <= i; j++)
                if (j * j == i)
                    cnt++;
        return cnt;
    }
 
    // Driver Code
    public static void Main()
    {
        int a = 9, b = 25;
        Console.Write("Count of squares is " + countSquares(a, b));
    }
}
 
// This code is contributed by Sam007

<?php
// A Simple Method to count squares
//between a and b
 
function countSquares($a, $b)
{
    $cnt = 0; // Initialize result
 
    // Traverse through all numbers
    for ($i = $a; $i <= $b; $i++)
 
        // Check if current number
        // 'i' is perfect square
        for ($j = 1; $j * $j <= $i;
                              $j++)
            if ($j * $j == $i)
                $cnt++;
 
    return $cnt;
}
 
// Driver code
 
    $a = 9; $b = 25;
    echo "Count of squares is ".
              countSquares($a, $b);
 
// This code is contributed by ajit.
?>

<script>
// A Simple Method to count squares
//between a and b
 
function countSquares(a, b)
{
   let cnt = 0;
    
    // Traverse through all numbers
    for (let i = a; i <= b; i++)
 
        // Check if current number
        // 'i' is perfect square
        for (let j = 1; j * j <= i;j++)
            if (j * j == i)
                cnt++;
 
    return cnt;
}
 
// Driver code
 
    let a = 9;
    let b = 25;
    document.write( "Count of squares is ",
              countSquares(a, b));
 
// This code is contributed by sravan.
</script>

Count of squares is 3

Un límite superior en el tiempo Complejidad de esta solución es O((ba) * sqrt(b)).
Método 2 (Eficiente) Simplemente podemos sacar la raíz cuadrada de ‘a’ y la raíz cuadrada de ‘b’ y contar los cuadrados perfectos entre ellos usando 
 

floor(sqrt(b)) - ceil(sqrt(a)) + 1

We take floor of sqrt(b) because we need to consider 
numbers before b.

We take ceil of sqrt(a) because we need to consider 
numbers after a.


For example, let b = 24, a = 8.  floor(sqrt(b)) = 4, 
ceil(sqrt(a)) = 3.  And number of squares is 4 - 3 + 1
= 2. The two numbers are 9 and 16.

A continuación se muestra la implementación de la idea anterior:
 

// An Efficient Method to count squares between a and b
#include <bits/stdc++.h>
using namespace std;
 
// An efficient solution to count square between a
// and b
int countSquares(int a, int b)
{
    return (floor(sqrt(b)) - ceil(sqrt(a)) + 1);
}
 
// Driver code
int main()
{
    int a = 9, b = 25;
    cout << "Count of squares is "
         << countSquares(a, b);
    return 0;
}

// An Efficient method to count squares between
// a and b
class CountSquares {
    double countSquares(int a, int b)
    {
        return (Math.floor(Math.sqrt(b)) - Math.ceil(Math.sqrt(a)) + 1);
    }
}
 
// Driver Code
public class PerfectSquares {
    public static void main(String[] args)
    {
        int a = 9, b = 25;
        CountSquares obj = new CountSquares();
        System.out.print("Count of squares is " + (int)obj.countSquares(a, b));
    }
}

# An Efficient Method to count squares between a
# and b
import math
def CountSquares(a, b):
    return (math.floor(math.sqrt(b)) - math.ceil(math.sqrt(a)) + 1)
 
# Driver Code
a = 9
b = 25
print ("Count of squares is:", int(CountSquares(a, b)))

// C# program for efficient method
// to count squares between a & b
using System;
 
class GFG {
 
    // Function to count squares
    static double countSquares(int a, int b)
    {
        return (Math.Floor(Math.Sqrt(b)) - Math.Ceiling(Math.Sqrt(a)) + 1);
    }
 
    // Driver Code
    public static void Main()
    {
        int a = 9, b = 25;
        Console.Write("Count of squares is " + (int)countSquares(a, b));
    }
}
 
// This code is contributed by Sam007.

<?php
// An Efficient PHP code to count
// squares between a and b
 
// Method to count square
// between a and b
function countSquares($a, $b)
{
    return (floor(sqrt($b)) -
            ceil(sqrt($a)) + 1);
}
 
// Driver code
{
    $a = 9;
    $b = 25;
    echo "Count of squares is ",
           countSquares($a, $b);
    return 0;
}
// This code is contributed by nitin mittal.
?>

<script>
// A Simple Method to count squares
//between a and b
 
function countSquares(a, b)
{
   return (Math.floor(Math.sqrt(b)) -  Math.ceil(Math.sqrt(a)) + 1);
}
 
// Driver code
 
    let a = 9;
    let b = 25;
    document.write( "Count of squares is ",
              countSquares(a, b));
 
// This code is contributed by sravan.
</script>

Count of squares is 3

La complejidad temporal de esta solución es O(Log b). Una implementación típica de raíz cuadrada para un número n toma un tiempo igual a O(Log n) [Vea esto para una implementación de muestra de raíz cuadrada] 

Este artículo es una contribución de Rahul Aggarwal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.