1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
4. #include<limits.h>
5. #include <math.h>
6.  
7. static int N = 0; // size of 2d array = row count
8.  
9. int isPrime (int number)
10. {
11.         // function to check if the given integer is prime or not.
12.         // basicly checking all numbers smaller than square root of it
13.         if (number <= 1) return 0;
14.    
15.     int upto = floor(sqrt(number));
16.    
17.     if (number % 2 == 0 && number != 2) return 0;
18.    
19.     int i;
20.     for(i = 3; i <= upto; i += 2)
21.     {
22.         if (number % i == 0) return 0;
23.     }
24.     return 1;  
25. }
26.  
27. int maxSum (int array[N][N], int depth[N][N])
28. {
29.         int i;
30.         int j;
31.         // making all primes INT_MIN on the bottom line.
32.         for (i = 0; i < N; i++)
33.         {
34.                 if (isPrime(array[N-1][i])) array[N-1][i] = INT_MIN;
35.         }
36.        
37.         // starting from the (N-2)th line
38.         // iterating each element and if it is prime, making it INT_MIN
39.         // (it can be basically any negative number but in order to use this algorithm with negative numbers, its more logial to use INT_MIN)
40.         // if it is not a prime number than check its adjacents
41.         // if both its adjaents are INT_MIN that means we cannot go further beacuse they are prime
42.         // if they are not prime, check their depths and take the one which has more depth
43.         // if they have same depth, check which one is bigger and take that
44.         // add this chosen element to our element, and make our element's depth = (chosens's + 1)
45.         // in this way we can store all element's depths in an another 2d array
46.         // after doing this all the number is the triangle, we can see the maxSum in the root. mainarray[0][0]
47.        
48.        
49.         for (i = N-2; i >= 0; i--)
50.     {
51.         for (j = 0; j <= i; j++)
52.         {
53.             if (isPrime(array[i][j]))
54.                         {
55.                                 array[i][j] = INT_MIN;
56.                         }
57.                         else
58.                         {
59.                                 if (array[i+1][j] != INT_MIN || array[i+1][j+1] != INT_MIN)
60.                                 {
61.                                         if (depth[i+1][j] > depth[i+1][j+1])
62.                                         {
63.                                                 array[i][j] += array[i+1][j];
64.                                                 depth[i][j] = depth[i+1][j] + 1;
65.                                         }
66.                                         else if (depth[i+1][j+1] > depth[i+1][j])
67.                                         {
68.                                                 array[i][j] += array[i+1][j+1];
69.                                                 depth[i][j] = depth[i+1][j+1] + 1;
70.                                         }
71.                                         else
72.                                         {
73.                                                 if (array[i+1][j] > array[i+1][j+1])
74.                                                 {
75.                                                         array[i][j] += array[i+1][j];
76.                                                         depth[i][j] = depth[i+1][j] + 1;
77.                                                 }
78.                                                 else
79.                                                 {
80.                                                         array[i][j] += array[i+1][j+1];
81.                                                         depth[i][j] = depth[i+1][j+1] + 1;
82.                                                 }
83.                                         }
84.                                 }      
85.                         }
86.         }
87.     }
88.     return array[0][0];
89. }
90.  
91. int main (void)
92. {
93.         // asking file name and openning it
94.         FILE *fp;
95.         char dosya[20];
96.         printf("Name Of  The File (.txt): ");
97.         scanf ("%s", dosya);
98.         fp = fopen(dosya, "r");
99.         int n = 10000;
100.        
101.         char line[10000];
102.        
103.         // counting rows to create NXN 2d array
104.         while (fgets (line, n, fp) != NULL) N++;
105.        
106.         // reopen the file to read again from the top line
107.         fclose(fp);
108.         fp = fopen(dosya, "r");
109.        
110.         // mainarray to store the triange
111.         int mainarray[N][N];
112.        
113.         // depth array to store the depth of each element
114.         // we use it to dive as much as possible
115.         // at first all of them are zero
116.         int depth[N][N];
117.         int i;
118.         int j;
119.         for (i = 0; i < N; i++)
120.         {
121.                 for (j = 0; j < N; j++)
122.                 {
123.                         depth[i][j] = 0;
124.                 }
125.         }
126.        
127.         // reading the file line by line
128.         // seperate the elements by " "
129.         // convert integer and store in mainarray
130.         // make the rest of the line 0
131.         char delim[] = " ";
132.         int row = 0;
133.         int col = 0;
134.         while (fgets (line, n, fp) != NULL)
135.         {
136.                 char *ptr = strtok(line, delim);
137.                 mainarray[row][col] = atoi(ptr);
138.                
139.                 col++;
140.                 ptr = strtok(NULL, delim);
141.                 while (ptr != NULL)
142.                 {
143.                         mainarray[row][col] = atoi(ptr);
144.                         col++;
145.                         ptr = strtok(NULL, delim);
146.                 }
147.                 while (col < N)
148.                 {
149.                         mainarray[row][col] = 0;
150.                         col++;
151.                 }
152.                 row++;
153.                 col = 0;
154.         }
155.        
156.         // close the file and print the answer
157.         fclose(fp);
158.         printf("\n\nMaximum Sum in Maximum Depth: %d", maxSum(mainarray, depth));
159.         return 0;
160. }