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
using System ; using System . Collections . Generic ; class GFG { static Dictionary < int , int > ma = new Dictionary < int , int > ( ) ; static void primeFactorize ( int a ) { for ( int i = 2 ; i * i <= a ; i += 2 ) { int cnt = 0 ; while ( a % i == 0 ) { cnt ++ ; a /= i ; } ma . Add ( i , cnt ) ; } if ( a > 1 ) ma . Add ( a , 1 ) ; } static int commDiv ( int a , int b ) { primeFactorize ( a ) ; int res = 1 ; foreach ( KeyValuePair < int , int > m in ma ) { int cnt = 0 ; int key = m . Key ; int value = m . Value ; while ( b % key == 0 ) { b /= key ; cnt ++ ; } res *= ( Math . Min ( cnt , value ) + 1 ) ; } return res ; } static void Main ( ) { int a = 12 , b = 24 ; Console . WriteLine ( commDiv ( a , b ) ) ; } }