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
< ? php function gcd ( $ a , $ b ) { if ( ( $ a % $ b ) == 0 ) return $ b ; return gcd ( $ b , $ a % $ b ) ; } function firstFactorialDivisibleNumber ( $ x ) { $ i = 1 ; $ new_x = $ x ; for ( $ i = 1 ; $ i < $ x ; $ i ++ ) { $ new_x /= gcd ( $ i , $ new_x ) ; if ( $ new_x == 1 ) break ; } return $ i ; } function countFactorialXNotY ( $ x , $ y ) { return ( firstFactorialDivisibleNumber ( $ y ) - firstFactorialDivisibleNumber ( $ x ) ) ; } $ x = 15 ; $ y = 25 ; echo ( countFactorialXNotY ( $ x , $ y ) ) ; ? >