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

#define N 1000000

int prost(int n) {
	
	if( n < 2 ) return 0;            
        if( n == 2 ) return 1;
	if( n % 2 == 0 ) return 0;
	for(int i = 3; i <= sqrt(n); i+=2) 
		if( n % i == 0 ) return 0;
	
	return 1;
}

int compare(const void *a, const void *b) {
	
	return *(int*)a - *(int*)b;
}

int main(int argc, char **argv) {
	
	int *prosti = (int *)calloc(N / 2, sizeof(int));;
	int id, np, ukupno;
	MPI_Status status;
	
	MPI_Init(&argc, &argv);
	
	MPI_Comm_size(MPI_COMM_WORLD,&np);
	MPI_Comm_rank(MPI_COMM_WORLD,&id);
	
	int br = 0;
	for (int i = id + 2; i <= N; i += np)
		if( prost(i) )
			prosti[br++] = i;
	
	if (id != 0) {
		MPI_Send(&br, 1, MPI_INT, 0, 10, MPI_COMM_WORLD);
		MPI_Send(prosti, br, MPI_INT, 0, 10, MPI_COMM_WORLD);
	} else {
		ukupno = br;
		for (int i = 1; i < np; i++) {
			MPI_Recv(&br, 1, MPI_INT, i, 10, MPI_COMM_WORLD, &status);	
			MPI_Recv(prosti + ukupno, br, MPI_INT, i, 10, MPI_COMM_WORLD, &status);
			ukupno += br;
		}
		
		qsort(prosti, ukupno, sizeof(int), compare);
		
		int gap = 0;
		for (int i = 0; i < ukupno - 1; i++)
			if (prosti[i + 1] - prosti[i] > gap)
				gap = prosti[i + 1] - prosti[i];
				
		printf("Gap je: %d\n", gap);
	}
		
	MPI_Finalize();
	return 0;
}