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

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 zbirCifara(int t) {
    int zbir = 0;

    while (t > 0) {
        zbir += t % 10;
        t /= 10;
    }

    return zbir;
}

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);
    MPI_Status status;

    int A;

    if (id == 0) {
        printf("\n");
        printf("Unesi A:");
        scanf("%d", &A);
    }

    MPI_Bcast(&A, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);

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

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

    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 *greens = (int*) malloc((A)*sizeof(int));
    int z = 0;

    for (i = 0; i < k; i++) {
        if (isPrime(zbirCifara(primes[i]))) {
            greens[z++] = primes[i];
        }

    }

    if (id == 0) {
        int last = z;
        int j;
        int localZ;
        for (j = 1; j < np; j++) {
            MPI_Recv(&localZ, 1, MPI_INT, j, 20, MPI_COMM_WORLD, &status);
            MPI_Recv(&greens[last], localZ, MPI_INT, j, 21, MPI_COMM_WORLD, &status);
            last += localZ;
        }

        FILE *f = fopen("greensOut.dat", "w");

        for (i = 0; i < last; i++) {
            fprintf(f, "%d\n", greens[i]);
        }

    } else {
        MPI_Send(&z, 1, MPI_INT, 0, 20, MPI_COMM_WORLD);
        MPI_Send(greens, z, MPI_INT, 0, 21, MPI_COMM_WORLD);
    }


    err = MPI_Finalize();

    return 0;
}