Count ways to split N ! into two distinct co | 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 ; Calling sieve function ; Given N ; Function call
var MAXN = 1000000 var is_prime = Array ( MAXN ) . fill ( 0 ) ; var count_of_primes = Array ( MAXN ) . fill ( 0 ) ; function sieve ( ) { for ( var i = 3 ; i < MAXN ; i += 2 ) { is_prime [ i ] = 1 ; } for ( var i = 3 ; i * i < MAXN ; i += 2 ) { if ( is_prime [ i ] ) for ( var j = i * i ; j < MAXN ; j += i ) { is_prime [ j ] = 0 ; } } is_prime [ 2 ] = 1 ; for ( var i = 1 ; i < MAXN ; i ++ ) count_of_primes [ i ] = count_of_primes [ i - 1 ] + is_prime [ i ] ; } function power ( x , y , p ) { var result = 1 ; while ( y > 0 ) { if ( y & 1 == 1 ) result = ( result * x ) % p ; x = ( x * x ) % p ; y >>= 1 ; } return result ; } function numberOfWays ( N ) { var count = count_of_primes [ N ] - 1 ; var mod = 1000000007 ; var answer = power ( 2 , count , mod ) ; if ( N == 1 ) answer = 0 ; document . write ( answer ) ; } sieve ( ) ; var N = 7 ; numberOfWays ( N ) ;