Advertisement
jasonpogi1669

Count Distinct Divisor of 'n' with Prime Factorization using C++

Sep 4th, 2021
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(0);
  8.     int n;
  9.     cin >> n;
  10.     map<int, int> mp;
  11.     // perform prime factorization and store the frequency (exponent) of each prime divisor
  12.     int factor = 2;
  13.     while (n > 1) {
  14.         if (n % factor == 0) {
  15.             mp[factor]++;
  16.             n /= factor;
  17.         } else {
  18.             factor++;
  19.         }
  20.     }
  21.     // calculate the product of all frequencies (exponents) of the prime numbers
  22.     // don't forget to add one (1) to every frequency since prime numbers can be divided by one (1)
  23.     int ans = 1;
  24.     for (auto& x : mp) {
  25.         ans *= (x.second + 1);
  26.     }
  27.     cout << ans << '\n';
  28.     return 0;
  29. }
  30.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement