Smallest number S such that N is a factor of S factorial or S ! | 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 ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ull  unsigned long long NEW_LINE map < ull , int > primeFactors ( ull num ) { map < ull , int > ans ; for ( ull i = 2 ; i * i <= num ; i ++ ) { while ( num % i == 0 ) { num /= i ; ans [ i ] ++ ; } } if ( num > 1 ) ans [ num ] ++ ; return ans ; } 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 ) { for ( map < ull , int > :: iterator it = factors . begin ( ) ; it != factors . end ( ) ; ++ it ) { if ( legendre ( it -> first , num ) < it -> second ) return false ; } return true ; } ull search ( ull start , ull end , map < ull , int > & factors ) { ull mid = ( start + end ) / 2 ; if ( ! possible ( factors , mid ) ) return search ( mid + 1 , end , factors ) ; if ( start == mid ) return mid ; return search ( start , mid , factors ) ; } ull findFact ( ull num ) { map < ull , int > factors = primeFactors ( num ) ; return search ( 1 , num , factors ) ; } int main ( ) { cout << findFact ( 6 ) << " n " ; cout << findFact ( 997587429953 ) << " n " ; return 0 ; }