#include <iostream>
#include <cstdlib>
#include <mpi.h>

//#define DEBUG(x,y) cout << rank << ") " << x << y << endl;

using namespace std;

int main( int argc, char **argv ) {
    int rank, cpu_size, range_first, range_last;
    MPI_Status status;

    if ( argc != 2 ) {
        cout << argv[0] << ": max" << endl;
        return 1;
    }

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &cpu_size);

    /* Proces 0 rozsyla wszystkim procesom informacje o ich zakresach */
    if ( rank == 0 ) {
        int max_val = atoi(argv[1]),
            tab_split = max_val / cpu_size;

#ifdef DEBUG
        DEBUG("Max: ", max_val);
        DEBUG("Liczba procesow: ", cpu_size);
        DEBUG("Wielkosc czesci: ", tab_split);
#endif

        /* Podziel zakres od 1 ... MAX na X watkow */
        range_last = tab_split;
        range_first = 2;
        for ( int i = 1, sf = 2, sl = tab_split; i < cpu_size; i++ ) {
            sf = sl + 1;
            i == cpu_size - 1 ? sl = max_val : sl += tab_split;

            MPI_Send(&sf, 1, MPI_INT, i, 100, MPI_COMM_WORLD);
            MPI_Send(&sl, 1, MPI_INT, i, 100, MPI_COMM_WORLD);
        }
    }

    if ( rank != 0 ) {
        MPI_Recv(&range_first, 1, MPI_INT, 0, 100, MPI_COMM_WORLD, &status);
        MPI_Recv(&range_last, 1, MPI_INT, 0, 100, MPI_COMM_WORLD, &status);
    }

    int tab_size = range_last - range_first + 1;

#ifdef DEBUG
    DEBUG("Wielkosc tablicy: ", tab_size);
    DEBUG("Wartosc pocztkowa: ", range_first);
    DEBUG("Wartosc koncowa: ", range_last);
#endif

    /* Utworz sobie tablice na podstawie zakresu */
    int *tab = new int[tab_size];
    for ( int i = 0, t = range_first; i < tab_size; i++ )
        tab[i] = t++;

    bool end_of_work = false;
    int token_pos = 0,      /* Aktualna pozycja tokena w tablicy */
        token = 0,          /* Wartosc do kasacji */
        token_master = 0;   /* Numer procesu rozdajacego token */

    while ( ! end_of_work ) {
        /* Tylko mistrz wyznacza nowy token. Reszta procesow ten
         * token odczytuje */
        if ( rank == token_master ) {
            while ( token_pos < tab_size && (tab[token_pos] == 1 || tab[token_pos] == 0) )
                token_pos++;

            /* Jesli wyszlismy poza tablice, czas zmienic mistrza */
            if ( token_pos >= tab_size ) {
                token = (token_master+1) * -1;
                end_of_work = true;
            }
            else
                token = tab[token_pos++];

            // Rozeslij nowy token po reszcie procesow
            for ( int i = rank + 1; i < cpu_size; i++ )
                MPI_Send(&token, 1, MPI_INT, i, 100, MPI_COMM_WORLD);

#ifdef DEBUG
            DEBUG("Rozsylam token: ", token);
#endif
        } else
            MPI_Recv(&token, 1, MPI_INT, token_master, 100, MPI_COMM_WORLD, &status);

        // Ujemna wartosc tokena oznacza ID nowego mistrza
        if ( token < 0 ) {
            token_master = token * -1;
            continue;
        }

        /* Przelec cala tablice i skasuj wielokrotnosci tokena */
        for ( int i = token_pos; i < tab_size; i++ )
            if ( tab[i] && tab[i] % token == 0 ) {
                for ( int j = i; j < tab_size; j += token )
                      tab[j] = 0;

                break;
            }
    }

    cout << rank << ") WYNIK: ";
    for ( int i = 0; i < tab_size; i++ )
        if ( tab[i] != 0 )
            cout << tab[i] << ' ';
    cout << endl;

    MPI_Finalize();
}