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 ; $res = 1 ; Initialize result $x = $x % $p ; 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 Code
< ? php function largestPower ( $ n , $ p ) { $ x = 0 ; while ( $ n ) { $ n = ( int ) ( $ n / $ p ) ; $ x += $ n ; } return $ x ; } function power ( $ x , $ y , $ p ) { while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function modFact ( $ n , $ p ) { if ( $ n >= $ p ) return 0 ; $ res = 1 ; $ isPrime = array_fill ( 0 , $ n + 1 , true ) ; for ( $ i = 2 ; $ i * $ i <= $ n ; $ i ++ ) { if ( $ isPrime [ $ i ] ) { for ( $ j = 2 * $ i ; $ j <= $ n ; $ j += $ i ) $ isPrime [ $ j ] = 0 ; } } for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) { if ( $ isPrime [ $ i ] ) { $ k = largestPower ( $ n , $ i ) ; $ res = ( $ res * power ( $ i , $ k , $ p ) ) % $ p ; } } return $ res ; } $ n = 25 ; $ p = 29 ; echo modFact ( $ n , $ p ) ; ? >