fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define N 1000000
  4.  
  5. using namespace std;
  6. ll n, nt[N + 1]; 
  7.  
  8. void spf()
  9. {
  10.      nt[1] = 1; 
  11.      for(int i = 2; i*i <= N; i++)
  12.      {     
  13.           if(nt[i] == 0) 
  14.           {
  15.             nt[i] = i; 
  16.             if(1LL*i*i <= N)
  17.             {
  18.                 for(int j = i*i; j <= N; j+= i)
  19.                 {
  20.                     if(nt[j] == 0) nt[j] = i; 
  21.                 }
  22.             }
  23.           }
  24.      }
  25.      for(int i = 2; i <= N; i++) if(nt[i] == 0) nt[i] = i;
  26. }
  27.  
  28. ll calc(ll x)
  29. {
  30.      ll cnt = 0;
  31.      while(x > 1)
  32.      {
  33.            ll p = nt[x];   
  34.                 cnt++; 
  35.                 while(x % p == 0) x /=p; 
  36.      }
  37.      return cnt;
  38. }
  39.  
  40. int main() 
  41. {
  42.       spf();
  43.       cin >> n; 
  44.  
  45.       cout << calc(n) << '\n'; 
  46. }
Success #stdin #stdout 0.02s 11368KB
comments (?)
stdin
copy 
18
stdout
copy 
2
https://ideone.com/k7HUWH
language:
C++14 (clang 8.0)
created:
1 day 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!