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


const int N = 1000000;

int isPrime(int X) {

    if (X == 1) return 0;
    if (X == 2) return 1;

    int i;
    double limit = sqrt(X);

    for (i = 2; i <= limit; i++) {
        if (X % i == 0) {
            return 0;
        }
    }
    return 1;
}



int main(int argc, char **argv) {

    int err;
    int id, np;

    err = MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &id);
    MPI_Comm_size(MPI_COMM_WORLD, &np);

    int T = N / np;
    int L = 1 +  id * T;
    int R;

    if (id != np - 1) {
        R = T * (id + 1) + 1;
    } else {
        R = N;
    }


    int *primes = (int*) malloc((T/2)*sizeof(int));;
    int k = 0;
    int i;

    for (i = L; i <= R; i++) {
        if (isPrime(i)) {
            primes[k++] = i;
        }
    }

    int max = 0;
    int tren;

    for (i = 0; i < k-1; i++) {
        tren = primes[i+1] - primes[i];
        if (tren > max) {
            max = tren;
        }
    }


    int globalMax;

    MPI_Reduce(&max, &globalMax, 1, MPI_INT, MPI_MAX, 0, MPI_COMM_WORLD);

    if (id == 0) {
        printf("%d\n", globalMax);
    }


    err = MPI_Finalize();

    return 0;
}