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

#define FACTOR(x,y)	(!(y % x))
#define JOB		0
#define NUMBER		1

int slave(long long);
int master();

int main(int argc, char **argv) {
    long long number;
    int rank;

    /* Initialize MPI */
    MPI_Init(&argc, &argv);

    /* Get the number to factor */
    sscanf(argv[1], "%Ld", &number);

    /* Find out the MPI rank of the current process */
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);

    /* If rank is nonzero, then the process should run as a slave */
    if (rank)
	slaveProcess(rank);
    else
	master(number);

    /* We're done.  Finalize MPI then exit. */
    MPI_Finalize();
    return 0;
}

int slaveProcess(int rank) {
    long long vect[] = {1, 0}, n, stride, max;
    int size;
    MPI_Status status;

    MPI_Comm_size(MPI_COMM_WORLD,&size);

    stride = size * 2;

    /* Get the computation information from the master */
    MPI_Bcast(vect, 2, MPI_LONG_LONG_INT, 0, MPI_COMM_WORLD);
    
    while (vect[JOB]) {
	max = sqrt(vect[NUMBER]);

	/* Find the smallest factor of vect[NUMBER] in the stripe. */
	for (n = (rank * 2) + 3; n < max; n += stride) {
	    if (FACTOR(n, vect[NUMBER])) {
		goto SHORTCUT;
	    }
	}

	/* We didn't find one in the given subset, so the smallest
	   factor in this subset was the number itself (excluding
	   1, of course). */
	n = vect[NUMBER];
	
    SHORTCUT:
	/* Send the result back. */
	MPI_Gather(&n, 1, MPI_LONG_LONG_INT,	/* Send one integer */
		   NULL, 1, MPI_LONG_LONG_INT,	/* We're not getting anything back */
		   0, MPI_COMM_WORLD);	/* Send it to 0 on COMM_WORLD */

	/* Get a new message. */
	MPI_Bcast(vect, 2, MPI_LONG_LONG_INT, 0, MPI_COMM_WORLD);
    } 

    return 0;
}

long long masterProcess(long long number, long long size) {
    long long stride, max, n;

    stride = size * 2;
    max = sqrt(number);

    for (n = 3; n < max; n += stride) {
	if (FACTOR(n, number)) {
	    return n;
	}
    }

    return number;
}

int master(long long input) {
    long long vect[2], number = input, i, *factors, min = 1;
    int size;
    MPI_Status status;

    printf("Prime factors of %Ld:\n", number);

    MPI_Comm_size(MPI_COMM_WORLD, &size);

    factors = (long long*)malloc(size*sizeof(long long));

    /* First, eliminate 2 as a factor */
    while (FACTOR(2, number)) {
	printf("2\n");
	number >>= 1;
    }

    do {
	number = number / min;
	vect[JOB] = 1;
	vect[NUMBER] = number;

	MPI_Bcast(vect, 2, MPI_LONG_LONG_INT, 0, MPI_COMM_WORLD);

	min = masterProcess(number, size);

	MPI_Gather(&min, 1, MPI_LONG_LONG_INT,	/* Send one integer */
		   factors, 1, MPI_LONG_LONG_INT,	/* Recieve size integers in to factor */
		   0, MPI_COMM_WORLD);	/* Send them to 0 on COMM_WORLD */

	for(i = 0; i < size; i++){
	    if (factors[i] < min)
		min = factors[i];
	}

	printf("%Ld\n", min);
    } while (number != min);

    fflush(stdout);

    /* Terminate all slave processes */
    vect[JOB] = 0;
    MPI_Bcast(vect, 2, MPI_LONG_LONG_INT, 0, MPI_COMM_WORLD);

    free(factors);

    return 0;
}