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 code
def largestPower ( n , p ) : NEW_LINE INDENT x = 0 NEW_LINE while ( n ) : NEW_LINE INDENT n //= p NEW_LINE x += n NEW_LINE DEDENT return x NEW_LINE DEDENT def power ( x , y , p ) : NEW_LINE INDENT res = 1 NEW_LINE x = x % p NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def modFact ( n , p ) : NEW_LINE INDENT if ( n >= p ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT res = 1 NEW_LINE isPrime = [ 1 ] * ( n + 1 ) NEW_LINE i = 2 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( isPrime [ i ] ) : NEW_LINE INDENT for j in range ( 2 * i , n , i ) : NEW_LINE INDENT isPrime [ j ] = 0 NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT for i in range ( 2 , n ) : NEW_LINE INDENT if ( isPrime [ i ] ) : NEW_LINE INDENT k = largestPower ( n , i ) NEW_LINE res = ( res * power ( i , k , p ) ) % p NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 25 NEW_LINE p = 29 NEW_LINE print ( modFact ( n , p ) ) NEW_LINE DEDENT