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

int isPrime(int number);
int isCachedPrime(int number, int *primes, int primesSize);
void addToCache(int number, int *primes, int *primesSizePtr, int *primesIndexPtr, int *largestCacheIntPtr);
void checkThenAddToCache(int number, int *primes, int *primesSizePtr, int *primesIndexPtr, int *largestCacheIntPtr);
int *getThreePrimeAddends(int number, int *primes, int *primesSizePtr, int *primesIndexPtr, int *largestCacheIntPtr);
void printPrimeAddends(int *addends, int number);

int main(void) {

    int *primes = malloc( 10 * sizeof(int) );
    int primesSize = 10;
    int *primesSizePtr = &primesSize;
    int primesIndex = 0;
    int *primesIndexPtr = &primesIndex;
    int largestCacheInt = 0;
    int *largestCacheIntPtr = &largestCacheInt;

    int *addendsFor111 = getThreePrimeAddends(111, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
    printPrimeAddends(addendsFor111, 111);
    free(addendsFor111);

    int *addendsFor17 = getThreePrimeAddends(17, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
    printPrimeAddends(addendsFor17, 17);
    free(addendsFor17);

    int *addendsFor199 = getThreePrimeAddends(199, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
    printPrimeAddends(addendsFor199, 199);
    free(addendsFor199);

    int *addendsFor287 = getThreePrimeAddends(287, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
    printPrimeAddends(addendsFor287, 287);
    free(addendsFor287);

    int *addendsFor53 = getThreePrimeAddends(53, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
    printPrimeAddends(addendsFor53, 53);
    free(addendsFor53);

    free(primes);

    return 0;
}

int isPrime(int number) {
    int i;
    for (i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) {
            return 0;
        }
    }
    return 1;
}

int isCachedPrime(int number, int *primes, int primesSize) {
    int i;
    for (i = 0; i < primesSize; i++) {
        if (primes[i] == number) {
            return 1;
        }
    }
    return 0;
}

void addToCache(int number, int *primes, int *primesSizePtr, int *primesIndexPtr, int *largestCacheIntPtr) {
    primes[*primesIndexPtr] = number;
    *primesIndexPtr += 1;
    *largestCacheIntPtr = number;
    if (*primesIndexPtr == *primesSizePtr) {
        *primesSizePtr *= 2;
        int *newArray = realloc( primes, *primesSizePtr * sizeof(int) );
        if (!newArray) {
            printf("Insufficient memory");
            exit(1);
        }
        primes = newArray;
    }
}

void checkThenAddToCache(int number, int *primes, int *primesSizePtr, int *primesIndexPtr, int *largestCacheIntPtr) {
    if (number > *largestCacheIntPtr) {
        if (isPrime(number) == 1) {
            addToCache(number, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
        }
    }
}

int *getThreePrimeAddends(int number, int *primes, int *primesSizePtr, int *primesIndexPtr, int *largestCacheIntPtr) {

    int *addends = malloc( 3 * sizeof(int) );

    if (!addends) {
        printf("Insufficient memory");
        exit(1);
    }

    int x, y, z;

    for (x = 2; x < number; x++) {
        if (isCachedPrime(x, primes, *primesSizePtr) == 0) {
            checkThenAddToCache(x, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
        }
        if (isCachedPrime(x, primes, *primesSizePtr) == 1) {
            for (y = 2; y < number; y++) {
                if (isCachedPrime(y, primes, *primesSizePtr) == 0) {
                    checkThenAddToCache(y, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
                }
                if (isCachedPrime(y, primes, *primesSizePtr) == 1) {
                    for (z = 2; z < number; z++) {
                        if (isCachedPrime(z, primes, *primesSizePtr) == 0) {
                            checkThenAddToCache(z, primes, primesSizePtr, primesIndexPtr, largestCacheIntPtr);
                        }
                        if (isCachedPrime(z, primes, *primesSizePtr) == 1) {
                            if (x + y + z == number) {
                                addends[0] = x;
                                addends[1] = y;
                                addends[2] = z;
                                return addends;
                            }
                        }
                    }
                }
            }
        }
    }

    printf("addends not found for %d\n", number);
    free(addends);
    exit(1);
}

void printPrimeAddends(int *addends, int number) {
    printf("%d's prime addends: %d, %d, %d\n", number, addends[0], addends[1], addends[2]);
}