#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>
#include <math.h>

static int N = 0; // size of 2d array = row count

int isPrime (int number)
{
	// function to check if the given integer is prime or not.
	// basicly checking all numbers smaller than square root of it
	if (number <= 1) return 0;
    
    int upto = floor(sqrt(number));
    
    if (number % 2 == 0 && number != 2) return 0;
    
    int i;
    for(i = 3; i <= upto; i += 2)
    {
        if (number % i == 0) return 0;
    }
    return 1;	
}

int maxSum (int array[N][N], int depth[N][N])
{
	int i;
	int j;
	// making all primes INT_MIN on the bottom line.
	for (i = 0; i < N; i++)
	{
		if (isPrime(array[N-1][i])) array[N-1][i] = INT_MIN;
	}
	
	// starting from the (N-2)th line
	// iterating each element and if it is prime, making it INT_MIN 
	// (it can be basically any negative number but in order to use this algorithm with negative numbers, its more logial to use INT_MIN)
	// if it is not a prime number than check its adjacents
	// if both its adjaents are INT_MIN that means we cannot go further beacuse they are prime
	// if they are not prime, check their depths and take the one which has more depth
	// if they have same depth, check which one is bigger and take that
	// add this chosen element to our element, and make our element's depth = (chosens's + 1)
	// in this way we can store all element's depths in an another 2d array
	// after doing this all the number is the triangle, we can see the maxSum in the root. mainarray[0][0]
	
	
	for (i = N-2; i >= 0; i--) 
    { 
    	for (j = 0; j <= i; j++) 
    	{ 
            if (isPrime(array[i][j])) 
			{
				array[i][j] = INT_MIN;
			}
			else
			{
				if (array[i+1][j] != INT_MIN || array[i+1][j+1] != INT_MIN)
				{
					if (depth[i+1][j] > depth[i+1][j+1])
					{
						array[i][j] += array[i+1][j];
						depth[i][j] = depth[i+1][j] + 1;
					}
					else if (depth[i+1][j+1] > depth[i+1][j])
					{
						array[i][j] += array[i+1][j+1];
						depth[i][j] = depth[i+1][j+1] + 1;
					}
					else
					{
						if (array[i+1][j] > array[i+1][j+1]) 
						{
							array[i][j] += array[i+1][j];
							depth[i][j] = depth[i+1][j] + 1;
						}
						else
						{
							array[i][j] += array[i+1][j+1];
							depth[i][j] = depth[i+1][j+1] + 1;
						}
					} 
				}	
			}
        } 
    }
    return array[0][0]; 
}

int main (void)
{
	// asking file name and openning it
	FILE *fp;
	char dosya[20];
	printf("Name Of  The File (.txt): "); 
	scanf ("%s", dosya);
	fp = fopen(dosya, "r");
	int n = 10000;
	
	char line[10000];
	
	// counting rows to create NXN 2d array
	while (fgets (line, n, fp) != NULL) N++;
	
	// reopen the file to read again from the top line
	fclose(fp);
	fp = fopen(dosya, "r");
	
	// mainarray to store the triange
	int mainarray[N][N];
	
	// depth array to store the depth of each element
	// we use it to dive as much as possible
	// at first all of them are zero
	int depth[N][N];
	int i;
	int j;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			depth[i][j] = 0;
		}
	}
	
	// reading the file line by line
	// seperate the elements by " "
	// convert integer and store in mainarray
	// make the rest of the line 0
	char delim[] = " ";
	int row = 0;
	int col = 0;
	while (fgets (line, n, fp) != NULL)
	{
		char *ptr = strtok(line, delim);
		mainarray[row][col] = atoi(ptr);
		
		col++;
		ptr = strtok(NULL, delim);
		while (ptr != NULL)
		{
			mainarray[row][col] = atoi(ptr);
			col++;
			ptr = strtok(NULL, delim);
		}
		while (col < N)
		{
			mainarray[row][col] = 0;
			col++;
		}
		row++;
		col = 0;
	}
	
	// close the file and print the answer
	fclose(fp);
	printf("\n\nMaximum Sum in Maximum Depth: %d", maxSum(mainarray, depth));
	return 0;
}