Expressing factorial n as sum of consecutive numbers | Python 3 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
MAX = 50002 ; NEW_LINE primes = [ ] NEW_LINE def sieve ( ) : NEW_LINE INDENT isPrime = [ True ] * ( MAX ) NEW_LINE p = 2 NEW_LINE while p * p < MAX : NEW_LINE INDENT if ( isPrime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , MAX , p ) : NEW_LINE INDENT isPrime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT for p in range ( 2 , MAX ) : NEW_LINE INDENT if ( isPrime [ p ] ) : NEW_LINE INDENT primes . append ( p ) NEW_LINE DEDENT DEDENT DEDENT def power ( x , y ) : NEW_LINE INDENT count = 0 NEW_LINE z = y NEW_LINE while ( x >= z ) : NEW_LINE INDENT count += ( x // z ) NEW_LINE z *= y NEW_LINE DEDENT return count NEW_LINE DEDENT def modMult ( a , b , mod ) : NEW_LINE INDENT res = 0 NEW_LINE a = a % mod NEW_LINE while ( b > 0 ) : NEW_LINE INDENT if ( b % 2 == 1 ) : NEW_LINE INDENT res = ( res + a ) % mod NEW_LINE DEDENT a = ( a * 2 ) % mod NEW_LINE b //= 2 NEW_LINE DEDENT return res % mod NEW_LINE DEDENT def countWays ( n , m ) : NEW_LINE INDENT ans = 1 NEW_LINE for i in range ( 1 , len ( primes ) ) : NEW_LINE INDENT powers = power ( n , primes [ i ] ) NEW_LINE if ( powers == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT ans = modMult ( ans , powers + 1 , m ) % m NEW_LINE DEDENT if ( ( ( ans - 1 ) % m ) < 0 ) : NEW_LINE INDENT return ( ans - 1 + m ) % m NEW_LINE DEDENT else : NEW_LINE INDENT return ( ans - 1 ) % m NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT sieve ( ) NEW_LINE n = 4 NEW_LINE m = 7 NEW_LINE print ( countWays ( n , m ) ) NEW_LINE DEDENT