#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <mpi.h>

#define N 100000

int k, size;

int is_prime(int n) {
	if (n < 2) return 0;
	if (n == 2) return 1;

	int m = 2;

	while (m < n) {
		if (n % m == 0) return 0;
		++m;
	}

	return 1;
}

int get_idx_by_number(int n) {
	int a = (n - 3) / 2;
	return (a % size) * k + a / size;
}

int main(int argc, char** argv) {
	MPI_Status status;
	int rank;

	MPI_Init(&argc, &argv);

	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);

	int global_arr_size = (int) ceil((double)N / 2.0) - 1;
	int local_arr_size = (int) ceil((double)global_arr_size / (double)size);
	int *global_arr = (int *) calloc(global_arr_size, sizeof(int));
	int *local_arr = (int *) calloc(local_arr_size, sizeof(int));

	k = local_arr_size;

	// Odredjuje da li su neparni brojevi od 3 do N prosti i rezultat cuva u global_arr
	// Rezultat cuvam da se ne bi ponavljala provera da li je broj prost
	int j = 0;
	for (int i = rank + 1; i < N / 2; i += size) {
		local_arr[j] = is_prime((2 * i) + 1);
		j++;
	}

	MPI_Allgather(local_arr, local_arr_size, MPI_INT, global_arr, local_arr_size, MPI_INT, MPI_COMM_WORLD);

	// Broji koliko parova susednih neparnih prostih brojeva ima od 3 do N
	int local_count = 0;
	for (int i = rank + 1; i < N / 2 - 1; i += size) {
		if (global_arr[get_idx_by_number(2 * i + 1)]
			&& global_arr[get_idx_by_number(2 * (i + 1) + 1)]) {
			++local_count;
		}
	}

	int global_count;
	MPI_Reduce(&local_count, &global_count, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

	if (rank == 0) {
		printf("%d\n", global_count);
	}

	MPI_Finalize();
}