Common Divisors of Two Numbers | C ++ implementation of program ; Map to store the count of each prime factor of a ; Function that calculate the count of each prime factor of a number ; Function to calculate all common divisors of two given numbers a , b -- > input integer numbers ; Find count of each prime factor of a ; stores number of common divisors ; Find the count of prime factors of b using distinct prime factors of a ; Prime factor of common divisor has minimum cnt of both a and b ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; map < int , int > ma ; void primeFactorize ( int a ) { for ( int i = 2 ; i * i <= a ; i += 2 ) { int cnt = 0 ; while ( a % i == 0 ) { cnt ++ ; a /= i ; } ma [ i ] = cnt ; } if ( a > 1 ) { ma [ a ] = 1 ; } } int commDiv ( int a , int b ) { primeFactorize ( a ) ; int res = 1 ; for ( auto m = ma . begin ( ) ; m != ma . end ( ) ; m ++ ) { int cnt = 0 ; int key = m -> first ; int value = m -> second ; while ( b % key == 0 ) { b /= key ; cnt ++ ; } res *= ( min ( cnt , value ) + 1 ) ; } return res ; } int main ( ) { int a = 12 , b = 24 ; cout << commDiv ( a , b ) << endl ; return 0 ; }