No of Factors of n ! | C ++ program to count number of factors of n ; Sieve of Eratosthenes to mark all prime number in array prime as 1 ; Initialize all numbers as prime ; Mark composites ; Returns the highest exponent of p in n ! ; Returns the no of factors in n ! ; ans stores the no of factors in n ! ; Find all primes upto n ; Multiply exponent ( of primes ) added with 1 ; if p is a prime then p is also a prime factor of n ! ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long int ll ; void sieve ( int n , bool prime [ ] ) { for ( int i = 1 ; i <= n ; i ++ ) prime [ i ] = 1 ; prime [ 1 ] = 0 ; for ( int i = 2 ; i * i <= n ; i ++ ) { if ( prime [ i ] ) { for ( int j = i * i ; j <= n ; j += i ) prime [ j ] = 0 ; } } } int expFactor ( int n , int p ) { int x = p ; int exponent = 0 ; while ( ( n / x ) > 0 ) { exponent += n / x ; x *= p ; } return exponent ; } ll countFactors ( int n ) { ll ans = 1 ; bool prime [ n + 1 ] ; sieve ( n , prime ) ; for ( int p = 1 ; p <= n ; p ++ ) { if ( prime [ p ] == 1 ) ans *= ( expFactor ( n , p ) + 1 ) ; } return ans ; } int main ( ) { int n = 16 ; printf ( " Count ▁ of ▁ factors ▁ of ▁ % d ! ▁ is ▁ % lld STRNEWLINE " , n , countFactors ( n ) ) ; return 0 ; }