Dado un número x, la tarea es encontrar el primer número natural i cuyo factorial sea divisible por x.
Ejemplos:
Input : x = 10 Output : 5 5 is the smallest number such that (5!) % 10 = 0 Input : x = 16 Output : 6 6 is the smallest number such that (6!) % 16 = 0
Una solución simple es iterar de 1 a x-1 y para cada número verifico si i! es divisible por x.
C++
// A simple C++ program to find first natural
// number whose factorial divides x.
#include <bits/stdc++.h>
using namespace std;
// Returns first number whose factorial
// divides x.
int firstFactorialDivisibleNumber(int x)
{
int i = 1; // Result
int fact = 1;
for (i = 1; i < x; i++) {
fact = fact * i;
if (fact % x == 0)
break;
}
return i;
}
// Driver code
int main(void)
{
int x = 16;
cout << firstFactorialDivisibleNumber(x);
return 0;
}
Java
// A simple Java program to find first natural
// number whose factorial divides x
class GFG {
// Returns first number whose factorial
// divides x.
static int firstFactorialDivisibleNumber(int x)
{
int i = 1; // Result
int fact = 1;
for (i = 1; i < x; i++) {
fact = fact * i;
if (fact % x == 0)
break;
}
return i;
}
// Driver code
public static void main(String[] args)
{
int x = 16;
System.out.print(firstFactorialDivisibleNumber(x));
}
}
// This code is contributed by Anant Agarwal.
Python3
# A simple python program to find # first natural number whose # factorial divides x. # Returns first number whose # factorial divides x. def firstFactorialDivisibleNumber(x): i = 1; # Result fact = 1; for i in range(1, x): fact = fact * i if (fact % x == 0): break return i # Driver code x = 16 print(firstFactorialDivisibleNumber(x)) # This code is contributed # by 29AjayKumar
C#
// A simple C# program to find first natural
// number whose factorial divides x
using System;
class GFG {
// Returns first number whose factorial
// divides x.
static int firstFactorialDivisibleNumber(int x)
{
int i = 1; // Result
int fact = 1;
for (i = 1; i < x; i++) {
fact = fact * i;
if (fact % x == 0)
break;
}
return i;
}
// Driver code
public static void Main()
{
int x = 16;
Console.Write(
firstFactorialDivisibleNumber(x));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// A simple PHP program to find
// first natural number whose
// factorial divides x.
// Returns first number whose
// factorial divides x.
function firstFactorialDivisibleNumber($x)
{
// Result
$i = 1;
$fact = 1;
for ($i = 1; $i < $x; $i++)
{
$fact = $fact * $i;
if ($fact % $x == 0)
break;
}
return $i;
}
// Driver code
$x = 16;
echo(firstFactorialDivisibleNumber($x));
// This code is contributed by Ajit.
?>
Javascript
<script>
// A simple Javascript program to find first natural
// number whose factorial divides x.
// Returns first number whose factorial
// divides x.
function firstFactorialDivisibleNumber(x)
{
var i = 1; // Result
var fact = 1;
for (i = 1; i < x; i++)
{
fact = fact * i;
if (fact % x == 0)
break;
}
return i;
}
// Driver code
var x = 16;
document.write(firstFactorialDivisibleNumber(x));
// This code is contributed by noob2000.
</script>
Producción :
6
Si aplicamos este enfoque ingenuo, ¡no pasaríamos de 20! o 21! (long long int tendrá su límite superior).
Una mejor solución evita el desbordamiento. La solución se basa en las siguientes observaciones.
- ¡Si yo! es divisible por x, entonces (i+1)!, (i+2)!, … también son divisibles por x.
- Para un número x, todos los factoriales i! son divisibles por x cuando i >= x.
- Si un número x es primo, entonces ningún factorial debajo de x puede dividirlo ya que x no se puede formar con la multiplicación de números más pequeños.
A continuación se muestra el algoritmo
1) Run a loop for i = 1 to n-1
a) Remove common factors
new_x /= gcd(i, new_x);
b) Check if we found first i.
if (new_x == 1)
break;
2) Return i
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find first natural number
// whose factorial divides x.
#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
// divides 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;
}
// Driver code
int main(void)
{
int x = 16;
cout << firstFactorialDivisibleNumber(x);
return 0;
}
Java
// Efficient Java program to find first
// natural number whose factorial divides x.
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
// divides 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;
}
// Driver code
public static void main(String[] args)
{
int x = 16;
System.out.print(firstFactorialDivisibleNumber(x));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find first natural number # whose factorial divides x. # 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 # divides x. def firstFactorialDivisibleNumber(x): i = 1 # Result 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 # Driver code def main(): x = 16 print(firstFactorialDivisibleNumber(x)) if __name__ == '__main__': main() # This code is contributed by 29AjayKumar
C#
// Efficient C# program to find first
// natural number whose factorial
// divides x.
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 divides 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;
}
// Driver code
public static void Main()
{
int x = 16;
Console.Write(
firstFactorialDivisibleNumber(x));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find first
// natural number whose
// factorial divides x.
// 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 divides 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;
}
// Driver code
$x = 16;
echo(firstFactorialDivisibleNumber($x));
// This code is contributed by Ajit.
?>
Javascript
<script>
// Efficient Javascript program to find first
// natural number whose factorial
// divides x.
// 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 divides x.
function firstFactorialDivisibleNumber(x)
{
let i = 1; // Result
let new_x = x;
for (i = 1; i < x; i++)
{
// Remove common factors
new_x = parseInt(new_x / gcd(i, new_x), 10);
// We found first i.
if (new_x == 1)
break;
}
return i;
}
let x = 16;
document.write(firstFactorialDivisibleNumber(x));
// This code is contributed by divyeshrabadiya07.
</script>
Producción :
6
Otro enfoque que usa la biblioteca boost:
(agradeciendo a ajay0007 por contribuir con este enfoque)
Aquí usamos la biblioteca boost para calcular de manera eficiente el valor del factorial.
Requisito previo: boost-multiprecision-library
C++
// A cpp program for finding
// the Special Factorial Number
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;
// function for calculating factorial
cpp_int fact(int n)
{
cpp_int num = 1;
for (int i = 1; i <= n; i++)
num = num * i;
return num;
}
// function for check Special_Factorial_Number
int Special_Factorial_Number(int k)
{
for(int i = 1 ; i <= k ; i++ )
{
// call fact function and the
// Modulo with k and check
// if condition is TRUE then return i
if ( ( fact (i) % k ) == 0 )
{
return i;
}
}
}
//driver function
int main()
{
// taking input
int k = 16;
cout<<Special_Factorial_Number(k);
}
Java
// Java program for finding
// the Special Factorial Number
public class GFG {
// function for calculating factorial
static int fact(int n) {
int num = 1;
for (int i = 1; i <= n; i++) {
num = num * i;
}
return num;
}
// function for check Special_Factorial_Number
static int Special_Factorial_Number(int k) {
for (int i = 1; i <= k; i++) {
// call fact function and the
// Modulo with k and check
// if condition is TRUE then return i
if (fact(i) % k == 0) {
return i;
}
}
return 0;
}
//driver function
public static void main(String[] args) {
// taking input
int k = 16;
System.out.println(Special_Factorial_Number(k));
}
}
/*This code is contributed by Rajput-Ji*/
Python3
# Python 3 program for finding # the Special Factorial Number # function for calculating factorial def fact( n): num = 1 for i in range(1, n + 1): num = num * i return num # function for check Special_Factorial_Number def Special_Factorial_Number(k): for i in range(1, k + 1): # call fact function and the # Modulo with k and check # if condition is TRUE then return i if (fact(i) % k == 0): return i return 0 # Driver Code if __name__ == '__main__': # taking input k = 16 print(Special_Factorial_Number(k)) # This code is contributed by Rajput-Ji
C#
// C# program for finding
// the Special Factorial Number
using System;
public class GFG{
// function for calculating factorial
static int fact(int n) {
int num = 1;
for (int i = 1; i <= n; i++) {
num = num * i;
}
return num;
}
// function for check Special_Factorial_Number
static int Special_Factorial_Number(int k) {
for (int i = 1; i <= k; i++) {
// call fact function and the
// Modulo with k and check
// if condition is TRUE then return i
if (fact(i) % k == 0) {
return i;
}
}
return 0;
}
//driver function
public static void Main() {
// taking input
int k = 16;
Console.WriteLine(Special_Factorial_Number(k));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program for finding
// the Special Factorial Number
// function for calculating
// factorial
function fact($n)
{
$num = 1;
for ($i = 1; $i <= $n; $i++)
$num = $num * $i;
return $num;
}
// function for check
// Special_Factorial_Number
function Special_Factorial_Number($k)
{
for($i = 1 ; $i <= $k ; $i++ )
{
// call fact function and the
// Modulo with k and check
// if condition is TRUE
// then return i
if (( fact ($i) % $k ) == 0 )
{
return $i;
}
}
}
// Driver Code
$k = 16;
echo Special_Factorial_Number($k);
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program for finding the Special Factorial Number
// function for calculating factorial
function fact(n) {
let num = 1;
for (let i = 1; i <= n; i++) {
num = num * i;
}
return num;
}
// function for check Special_Factorial_Number
function Special_Factorial_Number(k) {
for (let i = 1; i <= k; i++) {
// call fact function and the
// Modulo with k and check
// if condition is TRUE then return i
if (fact(i) % k == 0) {
return i;
}
}
return 0;
}
// taking input
let k = 16;
document.write(Special_Factorial_Number(k));
</script>
Producción :
6
Complejidad de tiempo: O (n ^ 2) desde que se usa un bucle for en otro bucle for
Este artículo es una contribución de Shubham Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA