Expressing factorial n as sum of consecutive numbers | CPP program to count number of ways we can express a factorial as sum of consecutive numbers ; sieve of Eratosthenes to compute the prime numbers ; Store all prime numbers ; function to calculate the largest power of a prime in a number ; Modular multiplication to avoid the overflow of multiplication Please see below for details https : www . geeksforgeeks . org / how - to - avoid - overflow - in - modular - multiplication / ; Returns count of ways to express n ! as sum of consecutives . ; We skip 2 ( First prime ) as we need to consider only odd primes ; compute the largest power of prime ; if the power of current prime number is zero in N ! , power of primes greater than current prime number will also be zero , so break out from the loop ; multiply the result at every step ; subtract 1 to exclude the case of 1 being an odd divisor ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  50002 NEW_LINE vector < int > primes ; void sieve ( ) { bool isPrime [ MAX ] ; memset ( isPrime , true , sizeof ( isPrime ) ) ; for ( int p = 2 ; p * p < MAX ; p ++ ) { if ( isPrime [ p ] == true ) { for ( int i = p * 2 ; i < MAX ; i += p ) isPrime [ i ] = false ; } } for ( int p = 2 ; p < MAX ; p ++ ) if ( isPrime [ p ] ) primes . push_back ( p ) ; } long long int power ( long long int x , long long int y ) { long long int count = 0 ; long long int z = y ; while ( x >= z ) { count += ( x / z ) ; z *= y ; } return count ; } long long int modMult ( long long int a , long long int b , long long int mod ) { long long int res = 0 ; a = a % mod ; while ( b > 0 ) { if ( b % 2 == 1 ) res = ( res + a ) % mod ; a = ( a * 2 ) % mod ; b /= 2 ; } return res % mod ; } long long int countWays ( long long int n , long long int m ) { long long int ans = 1 ; for ( int i = 1 ; i < primes . size ( ) ; i ++ ) { long long int powers = power ( n , primes [ i ] ) ; if ( powers == 0 ) break ; ans = modMult ( ans , powers + 1 , m ) % m ; } if ( ( ( ans - 1 ) % m ) < 0 ) return ( ans - 1 + m ) % m ; else return ( ans - 1 ) % m ; } int main ( ) { sieve ( ) ; long long int n = 4 , m = 7 ; cout << countWays ( n , m ) ; return 0 ; }