NTP

17. Eratostenovo sito

  ————————————————–

  int n;
int p[1001000];
// p[k] = 0, ako k jeste prost
// p[k] = 1, ako k nije prost
int main() {
  int k, u;
scanf(“%d”, &n);
  k = 2;
  while (k * k <= n) {
   if (p[k] == 0) {
     u = 2 * k;
     while (u <= n) {
     p[u] = 1;
     u += k;
  }
}
k++;
  }
  u = 0;
  for (k = 2; k <= n; k++) {
   if (p[k] == 0) {
     printf(“%d\n”, k);
     u++;
    }
  }
  printf(“Broj prostih je %d\n”, u);
}