fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define mx 31700
  5. bitset<mx>bt;
  6. ll prime[mx];
  7. int e=-1;
  8. void sieve()
  9.     {
  10.         bt[0]=bt[1]=1;
  11.         prime[++e]=2;
  12.         for(int i=4;i<mx;i++)bt[i]=1;
  13.         for(int i=3;i*i<=mx;i+=2){
  14.             if(!bt[i]){
  15.                 prime[++e]=i;
  16.                 for(int j=i*i;j<mx;j+=i)bt[j]=1;
  17.             }
  18.         }
  19.         for(int i=179;i<mx;i+=2){
  20.             if(!bt[i])prime[++e]=i;
  21.         }
  22.     }
  23. ll F(ll n)
  24.     {
  25.         ll r=0;
  26.         int i=0;
  27.         while(i<=e && prime[i]*prime[i]<=n){
  28.             while(n%prime[i]==0){
  29.                 n/=prime[i];
  30.                 r+=(prime[i]-1);
  31.             }
  32.             i++;
  33.         }
  34.         if(n>1)r+=(n-1);
  35.         return r;
  36.     }
  37. int main()
  38.     {
  39.         sieve();
  40.         ll n;
  41.         while(scanf("%lld",&n) && n){
  42.             printf("%lld\n",F(n));
  43.         }
  44.         return 0;
  45.     }
  46.  
Success #stdin #stdout 0s 15488KB
comments (?)
stdin
copy 
1
2
3
4
5
6
7
8
9
10
123456789
987654321
1000000000
0
stdout
copy 
0
1
2
2
4
3
6
3
4
5
13717424
109739372
1953133
https://ideone.com/iKPn0E
language:
C++ (gcc 8.3)
created:
7 years 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!