Number of N length sequences whose product is M | Java implementation of the above approach ; Function to calculate the value of ncr effectively ; Initializing the result ; Multiply and divide simultaneously to avoid overflow ; Return the answer ; Function to return the number of sequences of length N such that their product is M ; Hashmap to store the prime factors of M ; Calculate the prime factors of M ; If i divides M it means it is a factor Divide M by i till it could be divided to store the exponent ; Increase the exponent count ; If the number is a prime number greater than sqrt ( M ) ; Initializing the ans ; Multiply the answer for every prime factor ; entry . getValue ( ) represents the exponent of every prime factor ; Return the result ; Driver code
import java . util . HashMap ; class geeks { public static int nCr ( int n , int r ) { int res = 1 ; for ( int i = 1 ; i <= r ; i ++ ) { res *= ( n - r + i ) ; res /= i ; } return res ; } public static int NoofSequences ( int N , int M ) { HashMap < Integer , Integer > prime = new HashMap < > ( ) ; for ( int i = 2 ; i <= Math . sqrt ( M ) ; i ++ ) { while ( M % i == 0 ) { if ( prime . get ( i ) == null ) prime . put ( i , 1 ) ; else { int x = prime . get ( i ) ; prime . put ( i , ++ x ) ; } M /= i ; } } if ( M > 1 ) { if ( prime . get ( M ) != null ) { int x = prime . get ( M ) ; prime . put ( M , ++ x ) ; } else prime . put ( M , 1 ) ; } int ans = 1 ; for ( HashMap . Entry < Integer , Integer > entry : prime . entrySet ( ) ) { ans *= ( nCr ( N + entry . getValue ( ) - 1 , N - 1 ) ) ; } return ans ; } public static void main ( String [ ] args ) { int N = 2 , M = 6 ; System . out . println ( NoofSequences ( N , M ) ) ; } }