fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define int long long int
  5. #define ld long double
  6. #define all(x) x.begin(), x.end()
  7. #define sortall(x) sort(all(x))
  8. #define endl '\n'
  9. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  10. template<class T>
  11. void printC (T Collection)
  12. {
  13.     for (auto&i:Collection)
  14.         cout << i << "\n";
  15.     // cout << '\n';
  16. }
  17.  
  18. /*
  19.  * Think twice, code once
  20.  * Think of different approaches to tackle a problem: write them down.
  21.  * Think of different views of the problem. don't look from only one side.
  22.  * don't get stuck in one approach.
  23.  * common mistakes: - over_flow
  24.  *                  - out_of_bound index
  25.  *                  - infinite loop
  26.  *                  - corner cases
  27.  *                  - duplication counting.
  28. */
  29.  
  30. set<int> factors(const int n)
  31. {
  32.     set<int> F;
  33.     for(int i = 1; i * i <= n; ++i)
  34.         if (n % i == 0)
  35.             F.insert(i), F.insert(n/i);
  36.     return F;
  37. }
  38.  
  39. bool isPrime(const int n)
  40. {
  41.     if (n == 2) return true;
  42.     if (n <= 1 || n % 2 == 0) return false;
  43.     for (int i = 3; i <= n; i += 2)
  44.         if (n % i == 0)
  45.             return false;
  46.     return true;
  47. }
  48.  
  49. bool tenfa3(int n)
  50. {
  51.     int cnt = 0;
  52.     for (int i = 2; i <= n; ++i)
  53.     {
  54.         bool flag = true;
  55.         while (n % i == 0)
  56.         {
  57.             n/=i;
  58.             if (flag)
  59.             {
  60.                 cnt++;
  61.                 flag = false;
  62.             }
  63.             if (cnt > 1)
  64.                 return false;
  65.         }
  66.     }
  67.     if (n > 1) cnt++;
  68.     return cnt == 1;
  69. }
  70.  
  71. void solve()
  72. {
  73.     int n; cin >> n;
  74.     if (isPrime(n))
  75.     {
  76.         cout << 1;
  77.         return;
  78.     }
  79.     set<int> F(factors(n));
  80.     F.erase(1);
  81.     // printC(F);
  82.     int cnt = 0;
  83.     for (auto&i:F)
  84.     {
  85.         if (n % i == 0 && (isPrime(i) || tenfa3(i)))
  86.         {
  87.             n/=i;
  88.             cnt++;
  89.         }
  90.     }
  91.     cout << cnt;
  92. }
  93.  
  94. int32_t main()
  95. {
  96. #ifndef ONLINE_JUDGE
  97.     freopen("input.txt", "r", stdin);
  98.     freopen("output.txt", "w", stdout);
  99.     freopen("Errors.txt", "w", stderr);
  100. #endif
  101.     fast
  102.     int t = 1;
  103.     // cin >> t;
  104.     while (t--)
  105.     {
  106.         solve();
  107.         if (t) cout << '\n';
  108.     }
  109.     cout << '\n';
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/QKHaAm
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!