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

#define MAX 100000000

#define TRUE 1
#define FALSE 0

int *initArray(int n){

    int *arr;
    arr = (int *) malloc(n * sizeof(int));
    return arr;
}

int kaperkars(int x, int d){

    int powNum = x * x;
    int rightSide = powNum % 10;
    powNum = powNum / 10;
    d = d - 1;
    int mult = 10;

    if( x != 0){

        while(d!=0){

        int digit = powNum % 10;
        powNum = powNum / 10;
        int tempMult = mult;

        while(digit == 0){
            digit = powNum % 10;
            powNum = powNum / 10;
            tempMult = tempMult * 10;
            d--;
            if(d == 0)
                break;
        }
        
        if(d == 0)
            break;

        if(tempMult != mult && digit != 0){
            rightSide = digit * tempMult + rightSide;
            mult = tempMult;
        }
        else{
            rightSide = digit * mult + rightSide;
        }

        mult = mult * 10;
        d--;

        }
    }

    // printf("x : %d\n", x);
    // printf("rightSide : %d\n", rightSide);
    // printf("powNum : %d\n", powNum);
    
    int sumOfBoth = powNum + rightSide;
    if(x == sumOfBoth){
        return TRUE;
    }

    return FALSE;
}

int getNumSize(int x){

    int count = 0;
    while(x != 0){
        x = x / 10;
        count ++;
    }

    return count;
}

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

    int rank, np;
    double elapsed_time;

    MPI_Init(&argc,&argv);

    MPI_Barrier(MPI_COMM_WORLD);

    elapsed_time = - MPI_Wtime();

    MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    MPI_Comm_size(MPI_COMM_WORLD,&np);

    int *array;
    int *globalArray;

    if(rank == 0){
        globalArray = initArray(MAX);
    }

    array = initArray(MAX);

    int count = 0;

    //kaperkars(55,2);

    for(int i = rank + 1; i < MAX ; i += np){
        
        int numSize = getNumSize(i);

        if(kaperkars(i,numSize)){
            array[i] = 1;
            printf("%d\n",i);
        }
    }

    MPI_Reduce(array,globalArray,MAX,MPI_INT,MPI_LOR,0,MPI_COMM_WORLD);
    // ODRADJEN SAMO DA BI BROJEVI BILI U REDOSLEDU, SMANJUJE PERFORMANSE ALI ODRZAVAMO REDOSLED
    MPI_Barrier(MPI_COMM_WORLD);
    elapsed_time += MPI_Wtime();

    if(rank == 0){

        FILE *f;

        f = fopen("out.txt","w");

        for(int i = 0; i < MAX ; i++){
            if(globalArray[i] == 1){
                fprintf(f,"%d\n",i);
            }
            
        }

        fprintf(f,"\ntimes:");
        //fprintf(f,"%f, ", elapsed_time);

        fclose(f);

        printf("Elapsed time : %f \n",elapsed_time);
        printf("Kaperkarovi brojevi su: \n");
        for(int i = 1; i < MAX; i++){
            if(globalArray[i]){
                printf("%d\n",i);
            }

        }
    }
    
    MPI_Finalize();

    return 0;
}