Given two integer numbers, the task is to find the count of all common divisors of given numbers?
Input : a = 12, b = 24 Output: 6 // all common divisors are 1, 2, 3, // 4, 6 and 12 Input : a = 3, b = 17 Output: 1 // all common divisors are 1 Input : a = 20, b = 36 Output: 3 // all common divisors are 1, 2, 4
Java
// Java implementation of program Â
class Test {     // method to calculate gcd of two numbers     static int gcd(int a, int b)     {         if (a == 0)             return b; Â
        return gcd(b % a, a);     }     // method to calculate all common divisors     // of two given numbers     // a, b --> input integer numbers     static int commDiv(int a, int b)     {         // find gcd of a, b         int n = gcd(a, b); Â
        // Count divisors of n.         int result = 0;         for (int i = 1; i <= Math.sqrt(n); i++) {             // if 'i' is factor of n             if (n % i == 0) {                 // check if divisors are equal                 if (n / i == i)                     result += 1;                 else                    result += 2;             }         }         return result;     } Â
    // Driver method     public static void main(String args[])     {         int a = 12, b = 24;         System.out.println(commDiv(a, b));     } } |
Output:
6
Time complexity: O(sqrt(n)) because for loop will run for sqrt(n) times and function to calculate gcd will take O(log(min(a,b))
Auxiliary Space: O(log(min(a,b)) due to recursive stack spaceÂ
Please refer complete article on Common Divisors of Two Numbers for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
