Count ways to split N ! into two distinct co | Python3 program for the above approach ; Maximum value of N ; Stores at each indices if given number is prime or not ; Stores count_of_primes ; Function to generate primes using Sieve of Eratsothenes ; Assume all odds are primes ; If a prime is encountered ; Mark all its multiples as non - prime ; Count primes <= MAXN ; Function to calculate ( x ^ y ) % p in O ( log y ) ; Utility function to count the number of ways N ! can be split into co - prime factors ; Driver Code ; Calling sieve function ; Given N ; Function call
import math NEW_LINE MAXN = 1000000 NEW_LINE is_prime = [ 0 ] * MAXN NEW_LINE count_of_primes = [ 0 ] * MAXN NEW_LINE def sieve ( ) : NEW_LINE INDENT for i in range ( 3 , MAXN , 2 ) : NEW_LINE INDENT is_prime [ i ] = 1 NEW_LINE DEDENT for i in range ( 3 , int ( math . sqrt ( MAXN ) ) , 2 ) : NEW_LINE INDENT if is_prime [ i ] : NEW_LINE INDENT for j in range ( i * i , MAXN , i ) : NEW_LINE INDENT is_prime [ j ] = 0 NEW_LINE DEDENT DEDENT DEDENT is_prime [ 2 ] = 1 NEW_LINE for i in range ( 1 , MAXN ) : NEW_LINE INDENT count_of_primes [ i ] = ( count_of_primes [ i - 1 ] + is_prime [ i ] ) NEW_LINE DEDENT DEDENT def power ( x , y , p ) : NEW_LINE INDENT result = 1 NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if y & 1 == 1 : NEW_LINE INDENT result = ( result * x ) % p NEW_LINE DEDENT x = ( x * x ) % p NEW_LINE y >>= 1 NEW_LINE DEDENT return result NEW_LINE DEDENT def numberOfWays ( N ) : NEW_LINE INDENT count = count_of_primes [ N ] - 1 NEW_LINE mod = 1000000007 NEW_LINE answer = power ( 2 , count , mod ) NEW_LINE if N == 1 : NEW_LINE INDENT answer = 0 NEW_LINE DEDENT print ( answer ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT sieve ( ) NEW_LINE N = 7 NEW_LINE numberOfWays ( N ) NEW_LINE DEDENT