Smallest number S such that N is a factor of S factorial or S ! | 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 ; Function 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 function
def primeFactors ( num ) : NEW_LINE INDENT ans = dict ( ) NEW_LINE i = 2 NEW_LINE while ( i * i <= num ) : NEW_LINE INDENT while ( num % i == 0 ) : NEW_LINE INDENT num //= i ; NEW_LINE if i not in ans : NEW_LINE ans [ i ] = 0 NEW_LINE ans [ i ] += 1 NEW_LINE DEDENT DEDENT if ( num > 1 ) : NEW_LINE if num not in ans : NEW_LINE INDENT ans [ num ] = 0 NEW_LINE DEDENT ans [ num ] += 1 NEW_LINE return ans ; NEW_LINE DEDENT def legendre ( factor , num ) : NEW_LINE INDENT count = 0 NEW_LINE fac2 = factor ; NEW_LINE while ( num >= factor ) : NEW_LINE INDENT count += num // factor ; NEW_LINE factor *= fac2 ; NEW_LINE DEDENT return count ; NEW_LINE DEDENT def possible ( factors , num ) : NEW_LINE INDENT for it in factors . keys ( ) : NEW_LINE INDENT if ( legendre ( it , num ) < factors [ it ] ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT return True ; NEW_LINE DEDENT def search ( start , end , factors ) : NEW_LINE INDENT mid = ( start + end ) // 2 ; NEW_LINE if ( not possible ( factors , mid ) ) : NEW_LINE INDENT return search ( mid + 1 , end , factors ) ; NEW_LINE DEDENT if ( start == mid ) : NEW_LINE INDENT return mid ; NEW_LINE DEDENT return search ( start , mid , factors ) ; NEW_LINE DEDENT def findFact ( num ) : NEW_LINE INDENT factors = primeFactors ( num ) ; NEW_LINE return search ( 1 , num , factors ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT print ( findFact ( 6 ) ) NEW_LINE print ( findFact ( 997587429953 ) ) NEW_LINE DEDENT