Common Divisors of Two Numbers | Python3 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
import math NEW_LINE ma = { } NEW_LINE def primeFactorize ( a ) : NEW_LINE INDENT sqt = int ( math . sqrt ( a ) ) NEW_LINE for i in range ( 2 , sqt , 2 ) : NEW_LINE INDENT cnt = 0 NEW_LINE while ( a % i == 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE a /= i NEW_LINE DEDENT ma [ i ] = cnt NEW_LINE DEDENT if ( a > 1 ) : NEW_LINE INDENT ma [ a ] = 1 NEW_LINE DEDENT DEDENT def commDiv ( a , b ) : NEW_LINE INDENT primeFactorize ( a ) NEW_LINE res = 1 NEW_LINE for key , value in ma . items ( ) : NEW_LINE INDENT cnt = 0 NEW_LINE while ( b % key == 0 ) : NEW_LINE INDENT b /= key NEW_LINE cnt += 1 NEW_LINE DEDENT res *= ( min ( cnt , value ) + 1 ) NEW_LINE DEDENT return res NEW_LINE DEDENT a = 12 NEW_LINE b = 24 NEW_LINE print ( commDiv ( a , b ) ) NEW_LINE