Count ways to split N ! into two distinct co | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  1000000 NEW_LINE int is_prime [ MAXN ] = { 0 } ; int count_of_primes [ MAXN ] = { 0 } ; void sieve ( ) { for ( int i = 3 ; i < MAXN ; i += 2 ) { is_prime [ i ] = 1 ; } for ( int i = 3 ; i * i < MAXN ; i += 2 ) { if ( is_prime [ i ] ) for ( int j = i * i ; j < MAXN ; j += i ) { is_prime [ j ] = 0 ; } } is_prime [ 2 ] = 1 ; for ( int i = 1 ; i < MAXN ; i ++ ) count_of_primes [ i ] = count_of_primes [ i - 1 ] + is_prime [ i ] ; } long long int power ( long long int x , long long int y , long long int p ) { long long result = 1 ; while ( y > 0 ) { if ( y & 1 == 1 ) result = ( result * x ) % p ; x = ( x * x ) % p ; y >>= 1 ; } return result ; } void numberOfWays ( int N ) { long long int count = count_of_primes [ N ] - 1 ; long long int mod = 1000000007 ; long long int answer = power ( 2 , count , mod ) ; if ( N == 1 ) answer = 0 ; cout << answer ; } int main ( ) { sieve ( ) ; int N = 7 ; numberOfWays ( N ) ; return 0 ; }