#include <bits/stdc++.h>
#define ALLNUM 100000000
using namespace std;

long long arr[ALLNUM + 1] = {0};

int main() {
  int k = 2;

  long start = clock();
  for (int i = 2; i <= ALLNUM;) {
    k = i;

    if (k * k > ALLNUM) {
      break;
    }

    int mark = k + k;
    while (mark <= ALLNUM) {
      arr[mark] = 1;
      mark += k;
    }

    i++;
    while (arr[i] != 0) {
      i++;
    }
  }
  long end = clock();

  int ans = 0;
  for (int i = 2; i <= ALLNUM; i++) {
    if (arr[i] == 0) {
      ans++;
    }
  }
  printf("%d\n", ans);
  cout << "\033[36mTotal: " << (end - start) / 1000.0 << " (sec)\033[0m"
       << endl;

  return 0;
}

#include <bits/stdc++.h>
#include <mpi.h>
#define ALLNUM 100000000
using namespace std;

long long arr[ALLNUM + 1] = {0};
long long ans = 0;

int main() {
  MPI_Init(NULL, NULL);
  int world_size, world_rank;
  MPI_Comm_size(MPI_COMM_WORLD, &world_size);
  MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);

  int size = ALLNUM / world_size;
  int from = world_rank * size;
  int to =
      (world_rank != world_size - 1 ? (world_rank + 1) * size - 1 : ALLNUM);

  int k = 2;
  arr[0] = 1;
  arr[1] = 1;

  double start = MPI_Wtime();
  for (int i = from; i <= to;) {
    MPI_Bcast(&k, 1, MPI_INT, 0, MPI_COMM_WORLD);

    if (k * k > ALLNUM) {
      break;
    }

    if (k < to) {
      int mark = from;

      while (mark % k != 0 || mark == 0) {
        mark += 1;
      }

      if (mark == k) {
        mark += k;
      }

      while (mark <= to) {
        arr[mark] = 1;
        mark += k;
      }  // marking

      i++;
      while (arr[i] != 0) {
        i++;
      }  // find K
    }

    int newK = i;
    MPI_Reduce(&newK, &k, 1, MPI_INT, MPI_MIN, 0, MPI_COMM_WORLD);
  }

  int count = 0;
  for (int i = from; i <= to; i++) {
    if (arr[i] == 0 && i != 0 && i != 1) {
      count++;
    }
  }

  MPI_Reduce(&count, &ans, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

  double end = MPI_Wtime();
  MPI_Finalize();

  if (world_rank == 0) {
    cout << ans << endl;
    cout << "\033[36mTotal: " << (end - start) << " (sec)\033[0m" << endl;
  }

  return 0;
}