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!