solution1

public class solutionClass {
    //given data
    public static int array[][]={{1,0,0,0},{8,4,0,0},{2,6,9,0},{8,5,9,3}};
    public static boolean elligible(int n){
        int i,c=0;
        for (i=1;i<=n;i++){
        if(n%i==0)
        c++;
        }
        // for non primes
        if(c==2)
        return false;
        else
        return true;
    }
    // max adjacent element
    public static int maxele(int n,int cfer){
        int maxele=0,j=0,c=cfer;
        for(j=c;j<4;j++){
        //check if no is non prime and largest adjacent no.
        if(array[n][j]>maxele&&elligible(array[n][j])&&j<=cfer+1)//c>=cref&&c<=cref+1(check)
        {
            maxele=array[n][j];
        }
        }
        return maxele;
    }
    // main method
    public static void main(String args[]) {
       
      int sum=0;
      int cref=0;
      for(int r=0;r<4;r++)
      {
        for(int c=0;c<=r;c++)
        {
            // check if no is 1.non prime, 2. adjacent 3.and follows best path
            if(array[r][c]>0 && elligible(array[r][c])&&c>=cref&&c<=cref+1&&array[r][c]==maxele(r,cref))
            {sum+=array[r][c];
            cref=c;
            //System.out.println(r+"=r and ="+c+cref);
            break;
            }
        }
        //System.out.println("new line max elemt"+maxele(r,cref));
    }
    //print the sum
    System.out.print("Sum="+sum);
}
}