Given two numbers x and y (x <= y), find out the total number of natural numbers, say i, for which i! is divisible by x but not y.

Examples :

Input : x = 2, y = 5 Output : 3 There are three numbers, 2, 3 and 4 whose factorials are divisible by x but not y. Input: x = 15, y = 25 Output: 5 5! = 120 % 15 = 0 && 120 % 25 != 0 6! = 720 % 15 = 0 && 720 % 25 != 0 7! = 5040 % 15 = 0 && 5040 % 25 != 0 8! = 40320 % 15 = 0 && 40320 % 25 != 0 9! = 362880 % 15 = 0 && 362880 % 25 != 0 So total count = 5 Input: x = 10, y = 15 Output: 0

For all numbers greater than or equal to y, their factorials are divisible by y. So all natural numbers to be counted must be less than y.

A **simple solution** is to iterate from 1 to y-1 and for every number i check if i! is divisible by x and not divisible by y. If we apply this naive approach, we wouldn’t go above 20! or 21! (long long int will have its upper limit)

A **better solution** is based on below post.

Find the first natural number whose factorial is divisible by x

We find the first natural numbers whose factorials are divisible by x! and y! using above approach. Let the first natural numbers whose factorials are divisible by x and y be **xf** and **yf** respectively. Our final answer would be yf – xf. This formula is based on the fact that if i! is divisible by a number x, then (i+1)!, (i+2)!, … are also divisible by x.

Below is the implementation.

## C++

`// C++ program to count natural numbers whose ` `// factorials are divisble by x but not y. ` `#include<bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// GCD function to compute the greatest ` `// divisor among a and b ` `int` `gcd(` `int` `a, ` `int` `b) ` `{ ` ` ` `if` `((a % b) == 0) ` ` ` `return` `b; ` ` ` `return` `gcd(b, a % b); ` `} ` ` ` `// Returns first number whose factorial ` `// is divisible by x. ` `int` `firstFactorialDivisibleNumber(` `int` `x) ` `{ ` ` ` `int` `i = 1; ` `// Result ` ` ` `int` `new_x = x; ` ` ` ` ` `for` `(i=1; i<x; i++) ` ` ` `{ ` ` ` `// Remove common factors ` ` ` `new_x /= gcd(i, new_x); ` ` ` ` ` `// We found first i. ` ` ` `if` `(new_x == 1) ` ` ` `break` `; ` ` ` `} ` ` ` `return` `i; ` `} ` ` ` `// Count of natural numbers whose factorials ` `// are divisble by x but not y. ` `int` `countFactorialXNotY(` `int` `x, ` `int` `y) ` `{ ` ` ` `// Return difference between first natural ` ` ` `// number whose factorial is divisible by ` ` ` `// y and first natural number whose factorial ` ` ` `// is divisible by x. ` ` ` `return` `(firstFactorialDivisibleNumber(y) - ` ` ` `firstFactorialDivisibleNumber(x)); ` `} ` ` ` `// Driver code ` `int` `main(` `void` `) ` `{ ` ` ` `int` `x = 15, y = 25; ` ` ` `cout << countFactorialXNotY(x, y); ` ` ` `return` `0; ` `} ` |

## Java

`// Java program to count natural numbers whose ` `// factorials are divisble by x but not y. ` ` ` `class` `GFG ` `{ ` ` ` `// GCD function to compute the greatest ` ` ` `// divisor among a and b ` ` ` `static` `int` `gcd(` `int` `a, ` `int` `b) ` ` ` `{ ` ` ` `if` `((a % b) == ` `0` `) ` ` ` `return` `b; ` ` ` `return` `gcd(b, a % b); ` ` ` `} ` ` ` ` ` `// Returns first number whose factorial ` ` ` `// is divisible by x. ` ` ` `static` `int` `firstFactorialDivisibleNumber(` `int` `x) ` ` ` `{ ` ` ` `int` `i = ` `1` `; ` `// Result ` ` ` `int` `new_x = x; ` ` ` ` ` `for` `(i = ` `1` `; i < x; i++) ` ` ` `{ ` ` ` `// Remove common factors ` ` ` `new_x /= gcd(i, new_x); ` ` ` ` ` `// We found first i. ` ` ` `if` `(new_x == ` `1` `) ` ` ` `break` `; ` ` ` `} ` ` ` `return` `i; ` ` ` `} ` ` ` ` ` `// Count of natural numbers whose factorials ` ` ` `// are divisble by x but not y. ` ` ` `static` `int` `countFactorialXNotY(` `int` `x, ` `int` `y) ` ` ` `{ ` ` ` `// Return difference between first natural ` ` ` `// number whose factorial is divisible by ` ` ` `// y and first natural number whose factorial ` ` ` `// is divisible by x. ` ` ` `return` `(firstFactorialDivisibleNumber(y) - ` ` ` `firstFactorialDivisibleNumber(x)); ` ` ` `} ` ` ` ` ` `// Driver code ` ` ` `public` `static` `void` `main (String[] args) ` ` ` `{ ` ` ` `int` `x = ` `15` `, y = ` `25` `; ` ` ` `System.out.print(countFactorialXNotY(x, y)); ` ` ` `} ` `} ` ` ` `// This code is contributed by Anant Agarwal. ` |

## Python3

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

## C#

`// C# program to count natural numbers whose ` `// factorials are divisble by x but not y. ` `using` `System; ` ` ` `class` `GFG ` `{ ` ` ` ` ` `// GCD function to compute the greatest ` ` ` `// divisor among a and b ` ` ` `static` `int` `gcd(` `int` `a, ` `int` `b) ` ` ` `{ ` ` ` `if` `((a % b) == 0) ` ` ` `return` `b; ` ` ` `return` `gcd(b, a % b); ` ` ` `} ` ` ` ` ` `// Returns first number whose factorial ` ` ` `// is divisible by x. ` ` ` `static` `int` `firstFactorialDivisibleNumber(` `int` `x) ` ` ` `{ ` ` ` `int` `i = 1; ` `// Result ` ` ` `int` `new_x = x; ` ` ` ` ` `for` `(i = 1; i < x; i++) ` ` ` `{ ` ` ` ` ` `// Remove common factors ` ` ` `new_x /= gcd(i, new_x); ` ` ` ` ` `// We found first i. ` ` ` `if` `(new_x == 1) ` ` ` `break` `; ` ` ` `} ` ` ` ` ` `return` `i; ` ` ` `} ` ` ` ` ` `// Count of natural numbers whose factorials ` ` ` `// are divisble by x but not y. ` ` ` `static` `int` `countFactorialXNotY(` `int` `x, ` `int` `y) ` ` ` `{ ` ` ` ` ` `// Return difference between first natural ` ` ` `// number whose factorial is divisible by ` ` ` `// y and first natural number whose factorial ` ` ` `// is divisible by x. ` ` ` `return` `(firstFactorialDivisibleNumber(y) - ` ` ` `firstFactorialDivisibleNumber(x)); ` ` ` `} ` ` ` ` ` `// Driver code ` ` ` `public` `static` `void` `Main () ` ` ` `{ ` ` ` `int` `x = 15, y = 25; ` ` ` ` ` `Console.Write(countFactorialXNotY(x, y)); ` ` ` `} ` `} ` ` ` `// This code is contributed by nitin mittal. ` |

## PHP

`<?php ` `// PHP program to count natural ` `// numbers whose factorials are ` `// divisble by x but not y. ` ` ` `// GCD function to compute the ` `// greatest divisor among a and b ` `function` `gcd(` `$a` `, ` `$b` `) ` `{ ` ` ` `if` `((` `$a` `% ` `$b` `) == 0) ` ` ` `return` `$b` `; ` ` ` `return` `gcd(` `$b` `, ` `$a` `% ` `$b` `); ` `} ` ` ` `// Returns first number whose ` `// factorial is divisible by x. ` `function` `firstFactorialDivisibleNumber(` `$x` `) ` `{ ` ` ` `// Result ` ` ` `$i` `= 1; ` ` ` `$new_x` `= ` `$x` `; ` ` ` ` ` `for` `(` `$i` `= 1; ` `$i` `< ` `$x` `; ` `$i` `++) ` ` ` `{ ` ` ` `// Remove common factors ` ` ` `$new_x` `/= gcd(` `$i` `, ` `$new_x` `); ` ` ` ` ` `// We found first i. ` ` ` `if` `(` `$new_x` `== 1) ` ` ` `break` `; ` ` ` `} ` ` ` `return` `$i` `; ` `} ` ` ` `// Count of natural numbers ` `// whose factorials are divisble ` `// by x but not y. ` `function` `countFactorialXNotY(` `$x` `, ` `$y` `) ` `{ ` ` ` `// Return difference between ` ` ` `// first natural number whose ` ` ` `// factorial is divisible by ` ` ` `// y and first natural number ` ` ` `// whose factorial is divisible by x. ` ` ` `return` `(firstFactorialDivisibleNumber(` `$y` `) - ` ` ` `firstFactorialDivisibleNumber(` `$x` `)); ` `} ` ` ` `// Driver code ` `$x` `= 15; ` `$y` `= 25; ` `echo` `(countFactorialXNotY(` `$x` `, ` `$y` `)); ` ` ` `// This code is contributed by Ajit. ` `?> ` |

**Output :**

5

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments