Find numbers with K odd divisors in a given range
Given two numbers a and b, and a number k which is odd. The task is to find all the numbers between a and b (both inclusive) having exactly k divisors.
Examples:
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
This problem has simple solution, here we are given that k is odd and we know that only perfect square numbers have odd number of divisors , so we just need to check all perfect square numbers between a and b, and calculate divisors of only those perfect square numbers.
C++
// 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
// 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
# 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#
// 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 // 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. ?> |
Javascript
<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> |
Output:
4
Time Complexity: O(nsqrtn) , where n is the range of a and b
Auxiliary Space: O(1)
This problem can be solved more efficiently. Please refer method 2 of below post for an efficient solution.
Number of perfect squares between two given numbers