Count ways to split N ! into two distinct co | Java 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 all primes upto MAXN ; Function to calculate ( x ^ y ) % p in O ( log y ) ; Utility function to count the number of ways N ! can be split into two co - prime factors ; Driver Code ; Calling sieve function ; Given N ; Function call
import java . util . * ; class GFG { static final int MAXN = 1000000 ; static int is_prime [ ] ; static int count_of_primes [ ] ; static void sieve ( ) { is_prime = new int [ MAXN ] ; count_of_primes = new int [ MAXN ] ; Arrays . fill ( is_prime , 0 ) ; Arrays . fill ( count_of_primes , 0 ) ; 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 ] == 1 ) { 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 ] ; } static long power ( long x , long y , long p ) { long result = 1 ; while ( y > 0 ) { if ( ( y & 1 ) == 1 ) result = ( result * x ) % p ; x = ( x * x ) % p ; y >>= 1 ; } return result ; } static void numberOfWays ( int N ) { long count = count_of_primes [ N ] - 1 ; long mod = 1000000007 ; long answer = power ( 2 , count , mod ) ; if ( N == 1 ) answer = 0 ; long ans = answer ; System . out . println ( ans ) ; } public static void main ( String [ ] args ) { sieve ( ) ; int N = 7 ; numberOfWays ( N ) ; } }