Anik_Akash

Relatives Prime uva

May 10th, 2021 (edited)
317
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace    std;                                                                                          
  3. #define pb           push_back
  4. #define mx           1000000009
  5.  
  6. typedef long long int       ll;
  7.  
  8. ll ans = 0;
  9. vector<ll>prime;
  10. bool vis[mx+2];  //mx is define in above of the code;
  11. void sieve() {
  12.     ll x=sqrt((int)mx);
  13.     for(ll i=3; i<=x; i+=2) {
  14.         if(vis[i]==0) {
  15.             for(ll j=i*i; j<mx; j+=2*i)
  16.                 vis[j]=1;
  17.         }
  18.     }
  19.     prime.pb(2);
  20.     for(ll i=3; i<mx; i+=2)
  21.         if(vis[i]==0)
  22.             prime.pb(i);
  23. }
  24.  
  25. vector<int>FactorList;
  26.  
  27. void PrimeFactorize( ll n)
  28. {
  29.    
  30.     for(ll i=0; prime[i]*prime[i]<=n; i++)
  31.     {
  32.         if(n%prime[i]==0)
  33.         {
  34.             while(n%prime[i]==0) n/=prime[i];
  35.           //  FactorList.pb(prime[i]);
  36.             ans = ans-ans/prime[i];
  37.         }
  38.     }
  39.     if(n>1) ans = ans-ans/n;
  40. }
  41.  
  42. int main()
  43. {
  44.         ssieve();
  45.        ll n;
  46.         while(scanf("%lld",&n)==1)
  47.         {
  48.             ans = n;
  49.             if(n==0)return 0;
  50.             PrimeFactorize(n);
  51.            // for(int i=0; i<FactorList.size(); i++)
  52.            // {
  53.            //      //cout<<ans<<" "<<ans/FactorList[i]<<endl;
  54.            //      ans = ans-(ans/FactorList[i]);
  55.  
  56.            // }
  57.            printf("%lld\n",ans);
  58.            // cout<<"Prime List: "<<endl;
  59.            // for(int i=0; i<FactorList.size(); i++) cout<<FactorList[i]<<" ";
  60.             ans = 0;
  61.         }
  62.     return 0;
  63. }          
  64.  
RAW Paste Data