Bisus

Untitled

Oct 6th, 2019
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdlib.h>
  2. int scanf(const char *, ...);
  3. int printf(const char *, ...);
  4. int f(unsigned int n);
  5.  
  6. /* Количество простых чисел, меньших n
  7.  */
  8. int f(unsigned int n)
  9. {
  10.     unsigned int i, j, res = 0;
  11.     char *a;
  12.  
  13.     a = (char *)malloc(n*sizeof(char));
  14.     if(a==0) {
  15.         free(a);
  16.         return -1;
  17.     }
  18.  
  19.     for(i = 0; i<n; i++) a[i] = 1;
  20.  
  21.     for(i = 2; i*i<n; i++)
  22.     {
  23.         if(a[i]==1)
  24.             for(j = i; j<=(unsigned int)(n/i); j++) a[j*i] = 0;
  25.     }
  26.  
  27.     //for(i = 0; i<n; i++) printf("%d\t%d\n", i, a[i]);
  28.  
  29.     for(i = 2; i<n; i++)
  30.         res += a[i];
  31.  
  32.     free(a);
  33.     return res;
  34. }
  35.  
  36. int main(void)
  37. {
  38.     unsigned int n;
  39.  
  40.     printf("n=");
  41.     if( scanf("%u", &n)==0 )
  42.     {
  43.         printf("Input error!\n");
  44.  
  45.         return 1;
  46.     }
  47.  
  48.     printf("Result: %d\n", f(n));
  49.  
  50.     return 0;
  51. }
RAW Paste Data