Number of factors of very large number N modulo M where M is any prime number | Python 3 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
from math import sqrt NEW_LINE mod = 1000000007 NEW_LINE def mult ( a , b ) : NEW_LINE INDENT return ( ( a % mod ) * ( b % mod ) ) % mod NEW_LINE DEDENT def calculate_factors ( n ) : NEW_LINE INDENT cnt = 0 NEW_LINE ans = 1 NEW_LINE while ( n % 2 == 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE n = n // 2 NEW_LINE DEDENT if ( cnt ) : NEW_LINE INDENT ans = mult ( ans , ( cnt + 1 ) ) NEW_LINE DEDENT for i in range ( 3 , int ( sqrt ( n ) ) , 2 ) : NEW_LINE INDENT cnt = 0 NEW_LINE while ( n % i == 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE n = n // i NEW_LINE DEDENT if ( cnt ) : NEW_LINE INDENT ans = mult ( ans , ( cnt + 1 ) ) NEW_LINE DEDENT DEDENT if ( n > 2 ) : NEW_LINE INDENT ans = mult ( ans , 2 ) NEW_LINE DEDENT return ans % mod NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 19374857 NEW_LINE mod = 17 NEW_LINE print ( calculate_factors ( n ) ) NEW_LINE DEDENT