Number of factors of very large number N modulo M where M is any prime number | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE ll mod = 1000000007 ; ll mult ( ll a , ll b ) { return ( ( a % mod ) * ( b % mod ) ) % mod ; } ll calculate_factors ( ll n ) { ll ans , cnt ; cnt = 0 ; ans = 1 ; while ( n % 2 == 0 ) { cnt ++ ; n = n / 2 ; } if ( cnt ) { ans = mult ( ans , ( cnt + 1 ) ) ; } for ( int i = 3 ; i <= sqrt ( n ) ; i += 2 ) { cnt = 0 ; while ( n % i == 0 ) { cnt ++ ; n = n / i ; } if ( cnt ) { ans = mult ( ans , ( cnt + 1 ) ) ; } } if ( n > 2 ) { ans = mult ( ans , ( 2 ) ) ; } return ans % mod ; } int main ( ) { ll n = 193748576239475639 ; mod = 17 ; cout << calculate_factors ( n ) << endl ; return 0 ; }