Florii11

Untitled

Dec 7th, 2020
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.80 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. long long f(int n)
  5. {
  6.     int *a=calloc(n+1,sizeof(int));
  7.     long long s=0;
  8.     int d=2;
  9.     int k=0;
  10.     long long p=d;
  11.     while(n/p)
  12.     {
  13.         k+=n/p;
  14.         p*=d;
  15.     }
  16.     s=s+k*d;
  17.     int x=d;
  18.     while(x<=n)
  19.     {
  20.         a[x]=1;
  21.         x+=d;
  22.     }
  23.     for(d=3; d<=n; d+=2)
  24.     {
  25.         if(a[d]==0)
  26.         {
  27.             k=0;
  28.             p=d;
  29.             while(n/p)
  30.             {
  31.                 k+=n/p;
  32.                 p*=d;
  33.             }
  34.             s=s+k*d;
  35.             x=3*d;
  36.             while(x<=n)
  37.             {
  38.                 a[x]=1;
  39.                 x+=d;
  40.             }
  41.         }
  42.     }
  43.     free(a);
  44.     return s;
  45. }
  46.  
  47. int main()
  48. {
  49.     int n;
  50.     scanf("%d",&n);
  51.     printf("%lld",f(n));
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment