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