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

int prime(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 digitsSum(int n)
{
	int s = 0;
	while( n )
	{
		s += n % 10;
		n /= 10;
	}

	return s;
}

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


int main(int argc, char *argv[])
{
	int A;
	int id; //Process rank
	int np; //Num of processes
	double elapsed_time;
	MPI_Status status;
	
	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &id);
	MPI_Comm_size(MPI_COMM_WORLD, &np);

	if( !id )
	{
		printf("Unesite broj do kog zelite da trazite zelene brojeve!\n");
		//scanf("%d",&A);
		A = 1000000;
	}	

	MPI_Barrier(MPI_COMM_WORLD);
	if( !id ) elapsed_time = - MPI_Wtime();


	MPI_Bcast(&A, 1, MPI_INT, 0, MPI_COMM_WORLD);
	int *primes = (int *) calloc( A, sizeof(int) );

	int *globalPrimes = (int *) malloc( A * sizeof(int) );
	
	for(int i = 2*id+3; i < A; i += 2*np)
		if( prime(i) ) primes[i] = 1;
		
	MPI_Allreduce(primes, globalPrimes, A, MPI_INT, MPI_LOR, MPI_COMM_WORLD);
		
	globalPrimes[2] = 1; // @ je prost broj, a nismo za parne ispitivali

	int *greens = (int *) malloc( A * sizeof(int) );

	int nGreens = 0;
	if( !id ) greens[nGreens++] = 2;

	for(int i = 2*id+3; i < A; i += 2*np)
		if((globalPrimes[digitsSum(i)] == 1) && (globalPrimes[i])) greens[nGreens++] = i;
	
	if ( id ) MPI_Send(greens, nGreens, MPI_INT, 0, 20, MPI_COMM_WORLD);
	else
	{
		int mySize = nGreens;

		for (int i = 1; i < np; i++)
		{
			MPI_Probe(i, 20, MPI_COMM_WORLD, &status);
			int size;
			MPI_Get_count(&status, MPI_INT, &size);//size = status.size;
			MPI_Recv(greens + mySize, size, MPI_INT, i, 20, MPI_COMM_WORLD, &status);
			mySize += size;
		}

		qsort( greens, mySize, sizeof(int), compare );


		elapsed_time += MPI_Wtime();
		printf("Elapsed time is %f \n", elapsed_time);

		FILE *fOut = fopen("Greens.dat", "w");
		for (int i = 0; i < mySize; i++) fprintf(fOut,"%d\n", greens[i]);
		fclose(fOut);
	}

	MPI_Finalize();
	
	return 0;
}