Cuenta números naturales cuyos factoriales son divisibles por x pero no por y

Dados dos números x e y (x <= y), encuentre el número total de números naturales, digamos i, para los cuales i! es divisible por x pero no por y. 
Ejemplos: 
 

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

Para todos los números mayores o iguales que y, sus factoriales son divisibles por y. Entonces, todos los números naturales que se cuentan deben ser menores que y.
Una solución simple es iterar de 1 a y-1 y para cada número verifico si i! es divisible por x y no divisible por y. Si aplicamos este enfoque ingenuo, ¡no pasaríamos de 20! o 21! (long long int tendrá su límite superior) 
Una mejor solución se basa en la publicación a continuación. 
Encuentra el primer número natural cuyo factorial es divisible por x 
¡Encontramos los primeros números naturales cuyos factoriales son divisibles por x! y yo! utilizando el enfoque anterior. Sean xf e yf los primeros números naturales cuyos factoriales son divisibles por x e yrespectivamente. Nuestra respuesta final sería yf – xf. Esta fórmula se basa en el hecho de que si i! es divisible por un número x, entonces (i+1)!, (i+2)!, … también son divisibles por x.
A continuación se muestra la implementación. 
 

// C++ program to count natural numbers whose
// factorials are divisible 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 divisible 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 program to count natural numbers whose
// factorials are divisible 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 divisible 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.

# Python 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
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 divisible 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# program to count natural numbers whose
// factorials are divisible 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 divisible 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 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
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 divisible
// 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.
?>

<script>
 
// Javascript program to Merge two sorted halves of
// array Into Single Sorted Array
 
    // 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)
    {
        let i = 1; // Result
        let 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 divisible 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   
 
        let x = 15, y = 25;
        document.write(countFactorialXNotY(x, y));
                     
</script>

Producción : 

5

Este artículo es una contribución de Shubham Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.