ddsnowboard / javaprojects Goto Github PK

So, my plan is to implement some memoization. I mentioned it in b51ba60, but I didn't put any details, and that's because I don't really have too many that I can articulate. I know that there should be a way to make an associative array that has primes as keys and lists of primes that sum to them (or maybe just the index of the first and last ones) as values. Getting this is not too clear though. I could do it dynamically, which would mean that every time there could be one, I check, and if there is, I load it and move on, and if it isn't, I remember that, calculate it manually, and put it in after. Or, and this is becoming more appealing in my mind as time goes on, I could do it at the beginning and then just use it later. This would mean that I would go through all the possible sequences and then put them in an array. Something kinda like this (kinda sorta pseudocode)

for i = 0 to BIGGEST_PRIME_INDEX
    for j = i to BIGGEST_PRIME_INDEX
        // if the sum of all those numbers is prime... 
            // (This line is Python)
            memo[sum([primes[m] for m in range(i, j)])] = Pair(i, j) 

This would create a huge array, memo, with all the numbers in it and how to get their sum. So I could generate all the primes, which isn't too fast, but I think would take not forever and would have a time complexity less than O(n^2) I think, and then do this, which would also be kinda slow, but would also scale better, and then I run through the array and find the biggest difference in the pair. This could work.

Now it's just a brute force, and that's slow. Someone might see this someday...