1. import java.io.File;
2. import java.io.FileNotFoundException;
3. import java.util.HashMap;
4. import java.util.Scanner;
5.  
6.  
7.  
8. public class main {
9.  
10.     static final String inputFileName = "input.txt"; //input file name which in current directory
11.     static HashMap<Integer,Boolean> primeList = new HashMap<>(); //create hashmap for keep prime number
12.  
13.  
14.     public static void main(String[] args) {
15.         int line = getTriangleLength();
16.  
17.         int arraySize = (line * (line + 1)) / 2;
18.  
19.         int[] triangle = new int[arraySize];
20.         int[] dynamicTriangle;
21.         int[] indexTable = new int[line];
22.  
23.         fillTriangle(triangle);
24.         dynamicTriangle = triangle.clone();
25.         fillIndexTable(indexTable,line);
26.  
27.  
28.  
29.  
30.         int maxSum = findMaxSum(triangle,dynamicTriangle,indexTable,line);
31.  
32.         System.out.println(maxSum);
33.     }
34.  
35.     static int findMaxSum(int[] triangle,int[] dynamicTriangle,int[] indexTable,int size){
36.         boolean leftChildIsPrime;
37.         boolean rightChildIsPrime;
38.         int leftChild;
39.         int rightChild;
40.         int index;
41.  
42.         for (int i = size-1; i > 0 ; i--) {
43.  
44.             for (int j = 0; j <i ; j++) {
45.                 index =indexTable[i];
46.                 leftChild = triangle[index+j];
47.                 rightChild = triangle[index+j+1];
48.                 leftChildIsPrime = isPrime(leftChild);
49.                 rightChildIsPrime = isPrime(rightChild);
50.  
51.                 if(!(leftChildIsPrime || rightChildIsPrime)){ //both non prime
52.                     dynamicTriangle[index+j-i] = dynamicTriangle[index+j-i] + Math.max(dynamicTriangle[index+j],dynamicTriangle[index+j+1]); //update parent on dynamic triangle
53.  
54.                 }else if(leftChildIsPrime && !rightChildIsPrime){ //only left is prime
55.                     dynamicTriangle[index+j-i] = dynamicTriangle[index+j-i] + dynamicTriangle[index+j+1];
56.  
57.                 }else if(!leftChildIsPrime){ //only right is prime
58.                     dynamicTriangle[index+j-i] = dynamicTriangle[index+j-i] + dynamicTriangle[index+j];
59.                 }
60.             }
61.         }
62.  
63.  
64.         return  dynamicTriangle[0];
65.     }
66.  
67.     static boolean isPrime(int key){
68.         if (primeList.containsKey(key)){
69.             return primeList.get(key);
70.         }
71.  
72.  
73.         for(int i=2;i<=Math.sqrt(key);i++){
74.             if(key%i==0){
75.                 return false;
76.             }
77.         }
78.         primeList.put(key,true);
79.         return true;
80.  
81.     }
82.  
83.  
84.     static int getTriangleLength(){
85.         int lineCounter  = 0;
86.         File file =
87.                 new File(inputFileName);
88.         try {
89.  
90.             Scanner sc = new Scanner(file);
91.  
92.             while (sc.hasNextLine()){
93.                 lineCounter++;
94.  
95.                 sc.nextLine();
96.  
97.             }
98.  
99.         }catch (FileNotFoundException e){
100.             e.printStackTrace();
101.         }
102.         return lineCounter;
103.  
104.     }
105.  
106.     static void fillTriangle(int[] triangle){
107.         int index=0;
108.         File file =
109.                 new File(inputFileName);
110.         try {
111.  
112.             Scanner sc = new Scanner(file);
113.  
114.             while (sc.hasNextInt()){
115.                 triangle[index] = sc.nextInt();
116.                 index++;
117.             }
118.  
119.         }catch (FileNotFoundException e){
120.             e.printStackTrace();
121.         }
122.  
123.     }
124.  
125.     static void fillIndexTable(int[] indexTable,int size){
126.         for (int i = 0; i <size ; i++) {
127.             indexTable[i] = (i*(i+1))/2;
128.         }
129.  
130.     }
131.  
132.  
133. }