Encuentra números con K divisores impares en un rango dado

Dados dos números a y b, y un número k que es impar. La tarea es encontrar todos los números entre a y b (ambos inclusive) que tengan exactamente k divisores.
Ejemplos: 
 

Input : a = 2, b = 49, k = 3
Output: 4
// Between 2 and 49 there are four numbers
// with three divisors
// 4 (Divisors 1, 2, 4), 9 (Divisors 1, 3, 9),
// 25 (Divisors 1, 5, 25} and 49 (1, 7 and 49)

Input : a = 1, b = 100, k = 9
Output: 2
// between 1 and 100 there are 36 (1, 2, 3, 4, 6, 9, 12, 18, 36)
// and 100 (1, 2, 4, 5, 10, 20, 25, 50, 100) having exactly 9 
// divisors

Este problema tiene una solución simple , aquí sabemos que k es impar y sabemos que solo los números cuadrados perfectos tienen un número impar de divisores, por lo que solo necesitamos verificar todos los números cuadrados perfectos entre a y b, y calcular los divisores de solo esos números perfectos. números cuadrados. 
 

// C++ program to count numbers with k odd
// divisors in a range.
#include<bits/stdc++.h>
using namespace std;
 
// Utility function to check if number is
// perfect square or not
bool isPerfect(int n)
{
    int s = sqrt(n);
 
    return (s*s == n);
}
 
// Utility Function to return count of divisors
// of a number
int divisorsCount(int n)
{
    // Note that this loop runs till square root
    int count=0;
    for (int i=1; i<=sqrt(n)+1; i++)
    {
        if (n%i==0)
        {
            // If divisors are equal, count it
            // only once
            if (n/i == i)
                count += 1;
 
            // Otherwise print both
            else
                count += 2;
        }
    }
    return count;
}
 
// Function to calculate all divisors having
// exactly k divisors  between a and b
int kDivisors(int a,int b,int k)
{
    int count = 0; // Initialize result
 
    // calculate only for perfect square numbers
    for (int i=a; i<=b; i++)
    {
        // check if number is perfect square or not
        if (isPerfect(i))
 
            // total divisors of number equals to
            // k or not
            if (divisors(i) == k)
                count++;
 
    }
    return count;
}
 
// Driver program to run the case
int main()
{
    int a = 2, b = 49, k = 3;
    cout << kDivisors(a, b, k);
    return 0;
}

// Java program to count numbers
// with k odd divisors in a range.
import java.io.*;
import java.math.*;
 
class GFG {
     
    // Utility function to check if
    // number is perfect square or not
    static boolean isPerfect(int n)
    {
        int s = (int)(Math.sqrt(n));
     
        return (s*s == n);
    }
     
    // Utility Function to return
    // count of divisors of a number
    static int divisorsCount(int n)
    {
        // Note that this loop
        // runs till square root
        int count=0;
         
      for (int i = 1; i <= Math.sqrt(n) + 1; i++)
      {
        if (n % i == 0)
        {
                 
            // If divisors are equal,
            // count it only once
            if (n / i == i)
                count += 1;
 
            // Otherwise print both
            else
                count += 2;
        }
      }
        return count;
    }
     
    // Function to calculate all
    // divisors having exactly k
    // divisors between a and b
    static int kDivisors(int a,int b,int k)
    {
        // Initialize result
        int count = 0;
     
        // calculate only for
        // perfect square numbers
        for (int i = a; i <= b; i++)
        {
            // check if number is
            // perfect square or not
            if (isPerfect(i))
     
                // total divisors of number
                // equals to k or not
                if (divisorsCount(i) == k)
                    count++;
     
        }
        return count;
    }
     
    // Driver program to run the case
    public static void main(String args[])
    {
        int a = 21, b = 149, k = 333;
        System.out.println(kDivisors(a, b, k));
    }
}
 
// This code is contributed by Nikita Tiwari.

# Python3 program to count numbers
# with k odd divisors in a range.
import math
 
# Utility function to check if number
# is perfect square or not
def isPerfect(n) :
    s = math.sqrt(n)
 
    return (s * s == n)
 
# Utility Function to return
# count of divisors of a number
def divisorsCount(n) :
     
    # Note that this loop runs till
    # square root
    count = 0
    for i in range(1, (int)(math.sqrt(n) + 2)) :
         
        if (n % i == 0) :
            # If divisors are equal,
            # count it only once
            if (n // i == i) :
                count = count + 1
 
            # Otherwise print both
            else :
                count = count + 2
         
    return count
     
# Function to calculate all divisors having
# exactly k divisors between a and b
def kDivisors(a, b, k) :
    count = 0 # Initialize result
 
    # calculate only for perfect square numbers
    for i in range(a, b + 1) :
         
        # check if number is perfect square or not
        if (isPerfect(i)) :
            # total divisors of number equals to
            # k or not
            if (divisorsCount(i) == k) :
                count = count + 1
 
    return count
 
# Driver program to run the case
a = 2
b = 49
k = 3
print(kDivisors(a, b, k))
 
# This code is contributed by Nikita Tiwari.

// C# program to count numbers with
// k odd divisors in a range.
using System;
 
class GFG {
     
    // Utility function to check if number
    // is perfect square or not
    static bool isPerfect(int n)
    {
        int s = (int)(Math.Sqrt(n));
     
        return (s * s == n);
    }
     
    // Utility Function to return
    // count of divisors of a number
    static int divisorsCount(int n)
    {
        // Note that this loop
        // runs till square root
        int count=0;
         
    for (int i = 1; i <= Math.Sqrt(n) + 1; i++)
    {
        if (n % i == 0)
        {
                 
            // If divisors are equal,
            // count it only once
            if (n / i == i)
                count += 1;
 
            // Otherwise print both
            else
                count += 2;
        }
    }
        return count;
    }
     
    // Function to calculate all
    // divisors having exactly k
    // divisors between a and b
    static int kDivisors(int a, int b,
                         int k)
    {
        // Initialize result
        int count = 0;
     
        // calculate only for
        // perfect square numbers
        for (int i = a; i <= b; i++)
        {
            // check if number is
            // perfect square or not
            if (isPerfect(i))
     
                // total divisors of number
                // equals to k or not
                if (divisorsCount(i) == k)
                    count++;
     
        }
        return count;
    }
     
    // Driver Code
    public static void Main(String []args)
    {
        int a = 21, b = 149, k = 333;
        Console.Write(kDivisors(a, b, k));
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to count numbers
// with k odd divisors in a range.
 
// function to check if number is
// perfect square or not
function isPerfect($n)
{
    $s = sqrt($n);
    return ($s * $s == $n);
}
 
// Function to return count
// of divisors of a number
function divisorsCount($n)
{
     
    // Note that this loop
    // runs till square root
    $count = 0;
    for ($i = 1; $i <= sqrt($n) + 1; $i++)
    {
        if ($n % $i == 0)
        {
             
            // If divisors are equal,
            // count it only once
            if ($n / $i == $i)
                $count += 1;
 
            // Otherwise print both
            else
                $count += 2;
        }
    }
    return $count;
}
 
// Function to calculate
// all divisors having
// exactly k divisors
// between a and b
function kDivisors($a, $b, $k)
{  
     
    // Initialize result
    $count = 0;
 
    // calculate only for
    // perfect square numbers
    for ($i = $a; $i <= $b; $i++)
    {
         
        // check if number is
        // perfect square or not
        if (isPerfect($i))
 
            // total divisors of
            // number equals to
            // k or not
            if (divisorsCount($i) == $k)
                $count++;
 
    }
    return $count;
}
 
    // Driver Code
    $a = 2;
    $b = 49;
    $k = 3;
    echo kDivisors($a, $b, $k);
     
// This code is contributed by nitin mittal.
?>

<script>
 
// JavaScript program to count numbers with
// k odd divisors in a range.
 
// Utility function to check if number
// is perfect square or not
function isPerfect(n)
{
    var s = parseInt((Math.sqrt(n)));
 
    return (s * s == n);
}
 
// Utility Function to return
// count of divisors of a number
function divisorsCount(n)
{
    // Note that this loop
    // runs till square root
    var count=0;
     
for (var i = 1; i <= parseInt(Math.sqrt(n)) + 1; i++)
{
 
    if (n % i == 0)
    {
             
        // If divisors are equal,
        // count it only once
        if (parseInt(n / i) == i)
            count += 1;
        // Otherwise print both
        else
            count += 2;
    }
}
 
    return count;
}
 
// Function to calculate all
// divisors having exactly k
// divisors between a and b
function kDivisors(a, b, k)
{
    // Initialize result
    var count = 0;
 
    // calculate only for
    // perfect square numbers
    for(var i = a; i <= b; i++)
    {
        // check if number is
        // perfect square or not
        if (isPerfect(i))
        {
            // total divisors of number
            // equals to k or not
            if (divisorsCount(i)==k)
            {
                count++;
            }
        }
 
    }
    return count;
}
 
// Driver Code
var a = 2, b = 49, k = 3;
document.write(kDivisors(a, b, k));
 
</script>

Producción:  

4

Complejidad de tiempo: O(nsqrtn), donde n es el rango de a y b
Espacio auxiliar: O(1)

Este problema se puede resolver de manera más eficiente. Consulte el método 2 de la publicación a continuación para obtener una solución eficiente.
Número de cuadrados perfectos entre dos números dados
Este artículo es una contribución de Aarti_Rathi y Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo 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.