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