Smallest number S such that N is a factor of S factorial or S ! | Java 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
import java . util . HashMap ; import java . util . Iterator ; import java . util . Set ; class Test { static HashMap < Long , Integer > primeFactors ( long num ) { HashMap < Long , Integer > ans = new HashMap < Long , Integer > ( ) { @ Override public Integer get ( Object key ) { if ( containsKey ( key ) ) { return super . get ( key ) ; } return 0 ; } } ; for ( long i = 2 ; i * i <= num ; i ++ ) { while ( num % i == 0 ) { num /= i ; ans . put ( i , ans . get ( i ) + 1 ) ; } } if ( num > 1 ) ans . put ( num , ans . get ( num ) + 1 ) ; ; 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 boolean possible ( HashMap < Long , Integer > factors , long num ) { Set < Long > s = factors . keySet ( ) ; Iterator < Long > itr = s . iterator ( ) ; while ( itr . hasNext ( ) ) { long temp = itr . next ( ) ; if ( legendre ( temp , num ) < factors . get ( temp ) ) return false ; } return true ; } static long search ( long start , long end , HashMap < Long , Integer > 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 ) { HashMap < Long , Integer > factors = primeFactors ( num ) ; return search ( 1 , num , factors ) ; } public static void main ( String args [ ] ) { System . out . println ( findFact ( 6 ) ) ; System . out . println ( findFact ( 997587429953L ) ) ; } }