Number of factors of very large number N modulo M where M is any prime number | javascript implementation to find the Number of factors of very large number N modulo M ; Function for modular multiplication ; Function to find the number of factors of large Number N ; Count the number of times 2 divides the number N ; Condition to check if 2 divides it ; Check for all the possible numbers that can divide it ; Loop to check the number of times prime number i divides it ; Condition to check if prime number i divides it ; Condition to check if N at the end is a prime number . ; Driver Code
mod = 1000000007 ; function mult ( a , b ) { return ( ( a % mod ) * ( b % mod ) ) % mod ; } function calculate_factors ( n ) { var ans , cnt ; cnt = 0 ; ans = 1 ; while ( n % 2 == 0 ) { cnt ++ ; n = n / 2 ; } if ( cnt % 2 == 1 ) { ans = mult ( ans , ( cnt + 1 ) ) ; } for ( i = 3 ; i <= Math . sqrt ( n ) ; i += 2 ) { cnt = 0 ; while ( n % i == 0 ) { cnt ++ ; n = n / i ; } if ( cnt % 2 == 1 ) { ans = mult ( ans , ( cnt + 1 ) ) ; } } if ( n > 2 ) { ans = mult ( ans , ( 2 ) ) ; } return ans % mod ; } var n = 193748576239475639 ; mod = 17 ; document . write ( calculate_factors ( n ) ) ;