Count natural numbers whose factorials are divisible by x but not y | C ++ program to 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 . ; int i = 1 ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( ( a % b ) == 0 ) return b ; return gcd ( b , a % b ) ; } int firstFactorialDivisibleNumber ( int x ) { int new_x = x ; for ( i = 1 ; i < x ; i ++ ) { new_x /= gcd ( i , new_x ) ; if ( new_x == 1 ) break ; } return i ; } int countFactorialXNotY ( int x , int y ) { return ( firstFactorialDivisibleNumber ( y ) - firstFactorialDivisibleNumber ( x ) ) ; } int main ( void ) { int x = 15 , y = 25 ; cout << countFactorialXNotY ( x , y ) ; return 0 ; }