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

int isCapre(int x)
{
    int digitCount=0,temp=x;
    while(temp)
    {
        temp=temp/10;
        digitCount++;
    }
    temp=x;
    int desniBroj=0;
    int kvadrat=x*x;
    int stepenBroja=1;
    for(int i=0;i<digitCount;i++)
    {
        desniBroj=desniBroj+kvadrat%10*stepenBroja;
        stepenBroja*=10;
        kvadrat/=10;
    }
    return (kvadrat+desniBroj)==x;
}

int main(int argc,char *argv[])
{
    unsigned limit=100000000;
    unsigned *foundNumbers=(unsigned*)malloc(limit*sizeof(unsigned));
    unsigned numberCount=0;
    int id,np;
    MPI_Init(&argc,&argv);
    MPI_Comm_rank(MPI_COMM_WORLD,&id);
    MPI_Comm_size(MPI_COMM_WORLD,&np);
    for(int i=id;i<limit;i+=np)
    {
        if(isCapre((unsigned)i))
        {
            foundNumbers[numberCount++]=(unsigned)i;
        }
    }
    if(id==0)
    {
        MPI_Status status;
        for(int i=0;i<numberCount;i++) printf("%d\n",foundNumbers[i]);
        for(int i=1;i<np;i++)
        {
            MPI_Probe(i,20,MPI_COMM_WORLD,&status);
            MPI_Get_count(&status,MPI_UNSIGNED,&numberCount);
            MPI_Recv(foundNumbers,numberCount,MPI_UNSIGNED,i,20,MPI_COMM_WORLD,NULL);
            for(int i=0;i<numberCount;i++) printf("%d\n",foundNumbers[i]);
        }
    }
    else{
        MPI_Send(foundNumbers,numberCount,MPI_UNSIGNED,0,20,MPI_COMM_WORLD);
    }
    MPI_Finalize();
    return 0;    
}