Advertisement
Saleh127

UVA 10820

Oct 19th, 2020
71
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 ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. ll phi[100000],mark[100000];
  6.  
  7. void phifun()
  8. {
  9. ll i,j,k,l;
  10. for(i=1;i<=50005;i++)
  11. {
  12. phi[i]=i;
  13. }
  14. for(i=2;i<=50005;i++)
  15. {
  16. if(mark[i]==0)
  17. {
  18. for(j=i;j<=50005;j+=i)
  19. {
  20. mark[j]=1;
  21. phi[j]=(phi[j]/i)*(i-1);
  22. }
  23. }
  24. }
  25. for(i=2;i<=50005;i++)
  26. {
  27. phi[i]=phi[i-1]+(phi[i]*2);
  28. }
  29. }
  30.  
  31. int main()
  32. {
  33. ios_base::sync_with_stdio(0);
  34. cin.tie(0);cout.tie(0);
  35.  
  36. phifun();
  37.  
  38. ll n;
  39. while(cin>>n && n)
  40. {
  41. cout<<phi[n]<<endl;
  42. }
  43.  
  44. return 0;
  45. }
  46.  
Advertisement
RAW Paste Data Copied
Advertisement