human
Write me a code to smallest number S such that N is a factor of S factorial or S ! and the other steps required given the following:
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"
How can the above be solved in Python?
assistant
#Here is code to smallest number S such that N is a factor of S factorial or S ! and the other steps required.
 def primeFactors ( num ) :
	ans = dict ( )
	i = 2
	while ( i * i <= num ) :
		while ( num % i == 0 ) :
			num //= i ;
			if i not in ans :
			ans [ i ] = 0
			ans [ i ] += 1
	if ( num > 1 ) :
	if num not in ans :
		ans [ num ] = 0
	ans [ num ] += 1
	return ans ;
def legendre ( factor , num ) :
	count = 0
	fac2 = factor ;
	while ( num >= factor ) :
		count += num // factor ;
		factor *= fac2 ;
	return count ;
def possible ( factors , num ) :
	for it in factors . keys ( ) :
		if ( legendre ( it , num ) < factors [ it ] ) :
			return False ;
	return True ;
def search ( start , end , factors ) :
	mid = ( start + end ) // 2 ;
	if ( not possible ( factors , mid ) ) :
		return search ( mid + 1 , end , factors ) ;
	if ( start == mid ) :
		return mid ;
	return search ( start , mid , factors ) ;
def findFact ( num ) :
	factors = primeFactors ( num ) ;
	return search ( 1 , num , factors ) ;
if __name__ == ' _ _ main _ _ ' :
	print ( findFact ( 6 ) )
	print ( findFact ( 997587429953 ) )