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

#define N 100000

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

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

	return 1;
}

int is_sum_of_primes(int n, int *is_prime_arr) {
	if (n == 4) return 1;

	for (int i = 3; i <= n / 2; i += 2) {
		if (is_prime_arr[n - i] && is_prime_arr[i]) {
			return 1;
		}
	}
	return 0;
}

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

	MPI_Init(&argc, &argv);

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

	int arr_size = (int) ceil((double) N / (double) size);
	int *local_is_prime_arr = (int *) calloc(arr_size, sizeof(int));
	int from = arr_size * rank;

	for (int i = 0; i < arr_size; ++i) {
		local_is_prime_arr[i] = is_prime(from + i);
	}

	int *is_prime_arr = (int *) calloc(arr_size * size, sizeof(int));

	MPI_Allgather(local_is_prime_arr, arr_size, MPI_INT, is_prime_arr, arr_size, MPI_INT, MPI_COMM_WORLD);

	int gb_conj = -1;
	for (int i = rank * 2 + 4; i <= N; i += size * 2) {
		if (!is_sum_of_primes(i, is_prime_arr)) {
			gb_conj = i;
			break;
		}
	}

	int result;
	MPI_Reduce(&gb_conj, &result, 1, MPI_INT, MPI_MAX, 0, MPI_COMM_WORLD);

	if (rank == 0) {
		if (result == -1) printf("Goldbach's conjecture vazi za brojeve do %d\n", N);
		else printf("Goldbach's conjecture ne vazi za broj %d\n", result);
	}

	MPI_Finalize();
}