Compute n ! under modulo p | Returns largest power of p that divides n ! ; Initialize result ; Calculate x = n / p + n / ( p ^ 2 ) + n / ( p ^ 3 ) + ... . ; Utility function to do modular exponentiation . It returns ( x ^ y ) % p ; Initialize result Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; Returns n ! % p ; Use Sieve of Eratosthenes to find all primes smaller than n ; Consider all primes found by Sieve ; Find the largest power of prime ' i ' that divides n ; Multiply result with ( i ^ k ) % p ; Driver method
function largestPower ( n , p ) { let x = 0 ; while ( n > 0 ) { n = parseInt ( n / p , 10 ) ; x += n ; } return x ; } function power ( x , y , p ) { let res = 1 ; x = x % p ; while ( y > 0 ) { if ( y % 2 == 1 ) { res = ( res * x ) % p ; } x = ( x * x ) % p ; } return res ; } function modFact ( n , p ) { if ( n >= p ) { return 0 ; } let res = 1 ; let isPrime = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) isPrime [ i ] = true ; for ( let i = 2 ; i * i <= n ; i ++ ) { if ( isPrime [ i ] ) { for ( let j = 2 * i ; j <= n ; j += i ) { isPrime [ j ] = false ; } } } for ( let i = 2 ; i <= n ; i ++ ) { if ( isPrime [ i ] ) { let k = largestPower ( n , i ) ; res = ( res * power ( i , k , p ) ) % p ; } } return res ; } let n = 25 , p = 29 ; document . write ( modFact ( n , p ) ) ;