Compute n ! under modulo p | C ++ program to Returns n % p using Sieve of Eratosthenes ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int largestPower ( int n , int p ) { int x = 0 ; while ( n ) { n /= p ; x += n ; } return x ; } int power ( int x , int y , int p ) { int res = 1 ; x = x % p ; while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } int modFact ( int n , int p ) { if ( n >= p ) return 0 ; int res = 1 ; bool isPrime [ n + 1 ] ; memset ( isPrime , 1 , sizeof ( isPrime ) ) ; for ( int i = 2 ; i * i <= n ; i ++ ) { if ( isPrime [ i ] ) { for ( int j = 2 * i ; j <= n ; j += i ) isPrime [ j ] = 0 ; } } for ( int i = 2 ; i <= n ; i ++ ) { if ( isPrime [ i ] ) { int k = largestPower ( n , i ) ; res = ( res * power ( i , k , p ) ) % p ; } } return res ; } int main ( ) { int n = 25 , p = 29 ; cout << modFact ( n , p ) ; return 0 ; }