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

/* MAX < 10^4 is OK */
#define MAX 100000
#define debug printf

double arrPrimes[ MAX ]; 
double fDistance = 1;

double mathBigMod(double x, double y) {
	// X mod Y == 0 or not ? 
	
	double div = floor(x/y); 
	x = x - y * div;
	
	return x;
	
}

int checkPrime(double prime) {
	double x; 
	double sqrt_prime = ceil(sqrt(prime));
	for ( x = 2; x <= sqrt_prime; x = x + 1.0 ) {
		if (mathBigMod( prime , x) == 0) {
			//debug("\nX = %.0lf Mod %.0lf is Zero " , prime  ,  x );
			return 0; // Not a prime
		}
	}
	
	if ( x > sqrt_prime) return 1; // It's a prime
}

void initData() {
	int i;
	for (i = 0; i  < MAX; i++) {
		arrPrimes[i] = 0;
	}
}


int main(int argc, char *argv[] ) 
{ 
	int nproc = 10, nrank = 0, N;
	double nStartPrime = 0, nStopPrime; 
	
	//double nStartPrime; 
	printf("Generate Primes - MPI PROGRAM ");
	
	MPI_Init( &argc, &argv );
	MPI_Comm_size( MPI_COMM_WORLD, &nproc );
	MPI_Comm_rank( MPI_COMM_WORLD, &nrank );
	
	if (nrank == 0) {	
		//printf("Prime number start from: "); scanf(nStartPrime);
		if (argc < 4) { 
			printf("USSAGE: prime <N> <StartNum> <StopNum> --StartNum should be odd number from 3"); 
			exit(0);
		}
	}
					
	N = atoi( argv[1] ); // How many primes is calculated ?
			
	if (N > MAX) { 
		printf("SORRY, we can not calculate more than %d primes (primes: {2^N + 1}) \n", MAX );
		exit(0); 
	}
			
	nStartPrime = atof( argv[2] ); // Prime number start from
	nStopPrime = atof( argv[3] );
	
	//if (nStartPrime > nStopPrime) exit(0); // Nothing to do
			
	if (nStartPrime < 3) nStartPrime = 3;
	if (ceil( nStartPrime/2.0 ) == floor( nStartPrime/2 )) nStartPrime += 1; // increase 1 to be a odd number
		
	debug("nStartPrime = %.0lf \n", nStartPrime );		
	
	// Reset arrPrimes[MAX]
	initData();
	
			
	// START MPI	
			
	
	// Check for N primes from global data
	double prime = 3;
	int i = 0; 
	
	if (nrank == 0) {
		// Send nStartPrime & nStopPrime to all process
		arrPrimes[0] = nStartPrime; 
		arrPrimes[1] = nStopPrime;
		
	}
	
	// Send nStartPrime & nStopPrime to all process
	debug("Call MPI_Bcast...\n");
	MPI_Bcast( &nStartPrime, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD );
	MPI_Bcast( &nStopPrime, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD );
	MPI_Bcast( &N, 1, MPI_INT, 0, MPI_COMM_WORLD );
	
	debug("Calculate primes...\n");
		
		// Receive nStartPrime & nStopPrime
		//nStartPrime = arrPrimes[ 0 ]; 
		//nStopPrime = arrPrimes[ 1 ];
		int w = nrank ; // nrank - 1; 
		prime = nStartPrime + 2*w; 	
		i = 0; // count primes
		
		int localN = N / nproc; 
	 
		while (i < localN  &&  prime <= nStopPrime ) {	 
			//prime = arrPrimes[ i ];
			//printf("\nX = %.0lf is ", prime ); 
			if (checkPrime( prime )) {
				printf("\nX = %.0lf PRIME", prime );  
				arrPrimes[ i ] = prime;	
				i++;
			} 
			else {
				//printf("\nX = %.0lf NOT", prime );  
			}
			prime += 2 * nproc; // Primes may be odd numbers
			
		}
		localN = i; 
	
	
	debug("Call MPI_Gather....\n");
	MPI_Gather( arrPrimes, N/nproc, MPI_DOUBLE, arrPrimes, N/nproc, MPI_DOUBLE, 0, MPI_COMM_WORLD );
	
		
	MPI_Finalize();
	
	printf("\nDONE\n");
	
	return 0;
}