Number Of Divisors (NOD)
Number of Divisors(NOD) Given N you have to find the number of divisors of N. Solution: Step 1: Generating Prime using Sieve of Eratosthenes Step 2: Count Divisors using prime factorization CODE: long long NOD_using_factorization ( long long n ) /// O(lof2(N)) { long long sqrtn = sqrt ( n ) ; long long tmp = 1 ,divisors = 1 ; for ( int i = 0 ; i < prime. size ( ) && prime [ i ] <= sqrtn ; i ++ ) { ///if ( sieve[n] == 0 ) break; ///*Checks if n is prime or not*/ Please comment This line if n > 1e7 if ( n % prime [ i ] == 0 ) { tmp = 1 ; while ( n % prime [ i ] == 0 ) { n / = prime [ i ] ; tmp ++ ; } divisors * = tmp ; sqrtn = sqrt ( n ) ; } } if ( n ! = 1 ) { divisors * = 2 ; } return divisors ; }