Count natural numbers whose factorials are divisible by x but not y | GCD function to compute the greatest divisor among a and b ; Returns first number whose factorial is divisible by x . ; Result ; Remove common factors ; We found first i . ; Count of natural numbers whose factorials are divisible by x but not y . ; Return difference between first natural number whose factorial is divisible by y and first natural number whose factorial is divisible by x . ; Driver code
def gcd ( a , b ) : NEW_LINE INDENT if ( ( a % b ) == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT return gcd ( b , a % b ) NEW_LINE DEDENT def firstFactorialDivisibleNumber ( x ) : NEW_LINE INDENT i = 1 NEW_LINE new_x = x NEW_LINE for i in range ( 1 , x ) : NEW_LINE INDENT new_x /= gcd ( i , new_x ) NEW_LINE if ( new_x == 1 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return i NEW_LINE DEDENT def countFactorialXNotY ( x , y ) : NEW_LINE INDENT return ( firstFactorialDivisibleNumber ( y ) - firstFactorialDivisibleNumber ( x ) ) NEW_LINE DEDENT x = 15 NEW_LINE y = 25 NEW_LINE print ( countFactorialXNotY ( x , y ) ) NEW_LINE