El menor número S tal que N es un factor de S factorial o S!

Dado un número N. ¡Tienes la tarea de encontrar el número S más pequeño, tal que N sea un factor de S! (S factorial). N puede ser muy grande.
Ejemplos: 
 

Input  : 6
Output : 3
The value of 3! is 6
This is the smallest number which can have 6 as a factor.

Input  : 997587429953
Output : 998957
If we calculate out 998957!, 
we shall find that it is divisible by 997587429953.
Factors of 997587429953 are 998957 and 998629.

Enfoque ingenuo 
Iteramos de 1 a N, calculando factorial en cada caso. Cuando encontramos un factorial que es capaz de tener N como factor, lo generamos. Este método será difícil de implementar para N grande, ya que el factorial puede llegar a ser muy grande. 
Complejidad temporal: O(N^2)
Enfoque ingenuo optimizado 
En lugar de iterar de 1 a N, utilizamos la búsqueda binaria. ¡Este sigue siendo un mal método, ya que todavía estamos tratando de calcular N! 
Complejidad temporal O(N log N)
Solución óptima 
Primero podemos calcular todos los factores primos de N. Luego reducimos nuestro problema a encontrar un factorial que tenga todos los factores primos de N, al menos tantas veces como aparecen en N. Luego buscamos binariamente los elementos del 1 al N. Podemos utilizar la fórmula de Legendrepara comprobar si el factorial de un número tiene todos los mismos factores primos. Entonces encontramos el menor de tales números.
 

// Program to find factorial that N belongs to
#include <bits/stdc++.h>
using namespace std;
 
#define ull unsigned long long
 
// Calculate prime factors for a given number
map<ull, int> primeFactors(ull num)
{
    // Container for prime factors
    map<ull, int> ans;
 
    // Iterate from 2 to i^2 finding all factors
    for (ull i = 2; i * i <= num; i++)
    {
        while (num % i == 0)
        {
            num /= i;
            ans[i]++;
        }
    }
 
    // If we still have a remainder
    // it is also a prime factor
    if (num > 1)
        ans[num]++;
    return ans;
}
 
// Calculate occurrence of an element
// in factorial of a number
ull legendre(ull factor, ull num)
{
    ull count = 0, fac2 = factor;
    while (num >= factor)
    {
        count += num / factor;
        factor *= fac2;
    }
    return count;
}
 
bool possible(map<ull, int> &factors, ull num)
{
    // Iterate through prime factors
    for (map<ull, int>::iterator it = factors.begin();
            it != factors.end(); ++it)
    {
        // Check if factorial contains less
        // occurrences of prime factor
        if (legendre(it->first, num) < it->second)
            return false;
    }
    return true;
}
 
// Function to binary search 1 to N
ull search(ull start, ull end, map<ull, int> &factors)
{
    ull mid = (start + end) / 2;
 
    // Prime factors are not in the factorial
    // Increase the lowerbound
    if (!possible(factors, mid))
        return search(mid + 1, end, factors);
 
    // We have reached smallest occurrence
    if (start == mid)
        return mid;
 
    // Smaller factorial satisfying
    // requirements may exist, decrease upperbound
    return search(start, mid, factors);
}
 
// Calculate prime factors and search
ull findFact(ull num)
{
    map<ull, int> factors = primeFactors(num);
    return search(1, num, factors);
}
 
// Driver function
int main()
{
    cout << findFact(6) << "n";
    cout << findFact(997587429953) << "n";
    return 0;
}

// Java Program to find factorial that N belongs to
 
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
 
class Test
{
    // Calculate prime factors for a given number
    static HashMap<Long, Integer> primeFactors(long num)
    {
         
        // Container for prime factors
        HashMap<Long, Integer> ans = new HashMap<Long, Integer>(){
            @Override
            public Integer get(Object key) {
                if(containsKey(key)){
                    return super.get(key);                         
            }
            return 0;
        }
    };
 
      
        // Iterate from 2 to i^2 finding all factors
        for (long i = 2; i * i <= num; i++)
        {
            while (num % i == 0)
            {
                num /= i;
                ans.put(i, ans.get(i)+1);
            }
        }
      
        // If we still have a remainder
        // it is also a prime factor
        if (num > 1)
            ans.put(num, ans.get(num)+1);;
        return ans;
    }
     
    // Calculate occurrence of an element
    // in factorial of a number
    static long legendre(long factor, long num)
    {
        long count = 0, fac2 = factor;
        while (num >= factor)
        {
            count += num / factor;
            factor *= fac2;
        }
        return count;
    }
      
    static boolean possible(HashMap<Long, Integer> factors, long num)
    {
        Set<Long> s = factors.keySet();
         
        // Iterate through prime factors
        Iterator<Long> itr = s.iterator();
         
        while (itr.hasNext()) {
            long temp = itr.next();
             // Check if factorial contains less
            // occurrences of prime factor
            if (legendre(temp, num) < factors.get(temp))
                return false;
        }
         
        return true;
    }
      
    // Method to binary search 1 to N
    static long search(long start, long end, HashMap<Long, Integer> factors)
    {
        long mid = (start + end) / 2;
      
        // Prime factors are not in the factorial
        // Increase the lowerbound
        if (!possible(factors, mid))
            return search(mid + 1, end, factors);
      
        // We have reached smallest occurrence
        if (start == mid)
            return mid;
      
        // Smaller factorial satisfying
        // requirements may exist, decrease upperbound
        return search(start, mid, factors);
    }
      
    // Calculate prime factors and search
    static long findFact(long num)
    {
        HashMap<Long, Integer>  factors = primeFactors(num);
        return search(1, num, factors);
    }
     
    // Driver method
    public static void main(String args[])
    {
        System.out.println(findFact(6));
        System.out.println(findFact(997587429953L));
    }
}
// This code is contributed by Gaurav Miglani

# Python Program to find factorial that N belongs to
 
# Calculate prime factors for a given number
def primeFactors(num):
 
    # Container for prime factors
    ans = dict()
    i = 2
     
    # Iterate from 2 to i^2 finding all factors
    while(i * i <= num):  
        while (num % i == 0):
            num //= i;
            if i not in ans:
              ans[i] = 0
            ans[i] += 1
 
    # If we still have a remainder
    # it is also a prime factor
    if (num > 1):
      if num not in ans:
        ans[num] = 0
      ans[num] += 1
    return ans;
 
# Calculate occurrence of an element
# in factorial of a number
def legendre(factor, num):
    count = 0
    fac2 = factor;
    while (num >= factor):   
        count += num // factor;
        factor *= fac2; 
    return count;
   
def possible(factors, num):
 
    # Iterate through prime factors
    for it in factors.keys():
 
        # Check if factorial contains less
        # occurrences of prime factor
        if (legendre(it, num) < factors[it]):
            return False;   
    return True;
 
# Function to binary search 1 to N
def search(start, end, factors):
    mid = (start + end) // 2;
 
    # Prime factors are not in the factorial
    # Increase the lowerbound
    if (not possible(factors, mid)):
        return search(mid + 1, end, factors);
 
    # We have reached smallest occurrence
    if (start == mid):
        return mid;
 
    # Smaller factorial satisfying
    # requirements may exist, decrease upperbound
    return search(start, mid, factors);
 
# Calculate prime factors and search
def findFact(num):
    factors = primeFactors(num);
    return search(1, num, factors);
 
# Driver function
if __name__=='__main__':
 
    print(findFact(6))
    print(findFact(997587429953))
     
# This code is contributed by pratham76.

// C# Program to find factorial that N belongs to
using System;
using System.Collections;
using System.Collections.Generic;
 
class Test
{
 
  // Calculate prime factors for a given number
  static Dictionary<long, int> primeFactors(long num)
  {
 
    // Container for prime factors
    Dictionary<long, int> ans = new Dictionary<long, int>();
 
    // Iterate from 2 to i^2 finding all factors
    for (long i = 2; i * i <= num; i++)
    {
      while (num % i == 0)
      {
        num /= i;
        if(!ans.ContainsKey(i))
        {
          ans[i] = 0;
        }
        ans[i]++;
      }
    }
 
    // If we still have a remainder
    // it is also a prime factor
    if (num > 1)
    {
      if(!ans.ContainsKey(num))
      {
        ans[num] = 0;
      }
      ans[num]++;
    }
    return ans;
  }
 
  // Calculate occurrence of an element
  // in factorial of a number
  static long legendre(long factor, long num)
  {
    long count = 0, fac2 = factor;
    while (num >= factor)
    {
      count += num / factor;
      factor *= fac2;
    }
    return count;
  }
 
  static bool possible(Dictionary<long, int> factors, long num)
  {
 
    foreach (int itr in factors.Keys)
    {
      // Check if factorial contains less
      // occurrences of prime factor
      if (legendre(itr, num) < factors[itr])
        return false;
    }      
    return true;
  }
 
  // Method to binary search 1 to N
  static long search(long start, long end, Dictionary<long, int> factors)
  {
    long mid = (start + end) / 2;
 
    // Prime factors are not in the factorial
    // Increase the lowerbound
    if (!possible(factors, mid))
      return search(mid + 1, end, factors);
 
    // We have reached smallest occurrence
    if (start == mid)
      return mid;
 
    // Smaller factorial satisfying
    // requirements may exist, decrease upperbound
    return search(start, mid, factors);
  }
 
  // Calculate prime factors and search
  static long findFact(long num)
  {
    Dictionary<long, int>  factors = primeFactors(num);
    return search(1, num, factors);
  }
 
  // Driver method
  public static void Main()
  {
    Console.WriteLine(findFact(6));
    Console.WriteLine(findFact(997587429953L));
  }
}
 
// This code is contributed by rutvik_56.

// JavaScript Program to find
// Smallest number S such that N is a
// factor of S factorial  or S!
 
// Calculate prime factors for a given number
function primeFactors(num){
     
    // Container for prime factors
    const ans = new Map();
 
    // Iterate from 2 to i^2 finding all factors
    for (let i = 2; i * i <= num; i++){
        while (num % i == 0){
            num /= i;
            if(ans.has(i)){
                ans.set(i, ans.get(i) + 1);
            }
            else{
                ans.set(i,1);
            }
        }
    }
 
    // If we still have a remainder
    // it is also a prime factor
    if (num > 1){
        if(ans.has(num)){
            ans.set(num, ans.get(num) + 1);
        }
        else{
            ans.set(num,1);
        }
    }
    return ans;
}
 
// Calculate occurrence of an element
// in factorial of a number
function legendre(factor,num){
    let count = 0;
    let fac2 = factor;
    while (num >= factor){
        count += Math.floor(num / factor);
        factor *= fac2;
    }
    return count;
}
 
function possible(factors,num){
    // Iterate through prime factors
    for (const [key, value] of factors.entries()){
        // Check if factorial contains less
        // occurrences of prime factor
        if (legendre(key, num) < value){
            return false;
        }     
    }
    return true;
}
 
// Function to binary search 1 to N
function search(start,end, factors){
     let mid = Math.floor((start + end) / 2);
 
    // Prime factors are not in the factorial
    // Increase the lowerbound
    if (!possible(factors, mid)){
        return search(mid + 1, end, factors);
    }
         
    // We have reached smallest occurrence
    if (start == mid){
        return mid;
    }
         
    // Smaller factorial satisfying
    // requirements may exist, decrease upperbound
    return search(start, mid, factors);
}
 
// Calculate prime factors and search
function findFact(num){
    let factors = primeFactors(num);
    return search(1, num, factors);
}
 
 
// Driver function
{
    console.log(findFact(6));
    console.log(findFact(997587429953));
    return 0;
}
 
// The code is contributed by Gautam goel (gautamgoel962)

Producción: 
 

3
998957

En ningún momento calculamos un factorial. Esto significa que no tenemos que preocuparnos de que el factorial sea demasiado grande para almacenarlo. 
La fórmula de Lagrange se ejecuta en O (Log N). 
La búsqueda binaria es O (Log N). 
Calcular factores primos es O(sqrt(N)) 
Iterar a través de factores primos es O(Log N).
La complejidad del tiempo se convierte en: O(sqrt(N) + (Log N)^3) Aditya Kamath
contribuye con este artículo . 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.