Advertisement
Saleh127

at 179C

Sep 19th, 2020
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maX 1000005
  5. ll ans[1000008];
  6.  
  7. vector<ll>p;
  8. bool marked[maX];
  9. void sieve()
  10. {
  11. for(ll i=4; i<=maX; i+=2)
  12. {
  13. marked[i]=1;
  14. }
  15.  
  16. p.push_back(2);
  17.  
  18. for(ll i=3; i<=maX; i+=2)
  19. {
  20. if(marked[i]==0)
  21. {
  22. p.push_back(i);
  23. for(ll j=i*i; j<=maX; j+=i+i)
  24. {
  25. marked[j]=1;
  26. }
  27. }
  28. }
  29. }
  30.  
  31. void div()
  32. {
  33. ll i,j,a,d,e;
  34.  
  35. ans[0]=0;
  36. ans[1]=1;
  37. for(i=2; i<1000001; i++)
  38. {
  39. a=i;
  40. d=1;
  41. for(j=0; (p[j]*p[j])<=a; j++)
  42. {
  43. if(a%p[j]==0)
  44. {
  45. e=1;
  46. while(a%p[j]==0)
  47. {
  48. e++;
  49. a/=p[j];
  50. }
  51. d*=e;
  52. }
  53. }
  54. if(a>1) d=d*2;
  55. ans[i]=d+ans[i-1];
  56. }
  57. }
  58.  
  59. int main()
  60. {
  61.  
  62. sieve();
  63. div();
  64.  
  65. ll x;
  66. cin>>x;
  67.  
  68. cout<<ans[x-1]<<endl;
  69.  
  70. return 0;
  71. }
  72.  
  73.  
  74.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement