I had posted a grotesque non-working solution to this previously, so here is a grotesque working solution.
Yes, it uses global variables and old-fashioned extra book-keeping, and the main function is just a step-wise procedural function, but it works and it's correct, so I'm going to leave it as is.
Statutory warning: Spoilers ahead
const MAX_NUM = 1000000
type Number struct {
isPrime bool
maxPrimeSum int
maxConsecutivePrimes int
previousPrimeIndex int
}
// Oh noez! A _global_ variable!
var numbers []Number
func markMultiples(p int) {
for n := 2 * p; n < len(numbers); n += p {
numbers[n].isPrime = false
}
}
func populatePrimes() {
// First mark all numbers as prime
for i := 0; i < len(numbers); i++ {
numbers[i].isPrime = true
}
// Bootstrap our loop with the first prime, 2
numbers[0].isPrime = false
numbers[1].isPrime = false
prevPrime := 2
numbers[2].isPrime = true
numbers[2].previousPrimeIndex = -1
// Straightforward sieve
markMultiples(prevPrime)
for p := 3; p < len(numbers); p++ {
if numbers[p].isPrime {
numbers[p].previousPrimeIndex = prevPrime
prevPrime = p
markMultiples(prevPrime)
}
}
}
func calculatePrimeSums() {
// Initialize first prime, then move out from there
numbers[2].maxPrimeSum = 2
numbers[2].maxConsecutivePrimes = 1
// As an upper limit for sums, what's the largest prime we have?
largestPrime := MAX_NUM
for i := MAX_NUM - 1; i > 0; i-- {
if numbers[i].isPrime {
largestPrime = i
break
}
}
fmt.Println("The largest possible prime to sum to is : ", largestPrime)
for i := 3; i < len(numbers); i++ {
if !numbers[i].isPrime {
continue
}
sum := 0
numPrimesTried := 0
lastPrimeSum := 0
numPrimesInSum := 0
// Go back through the sequence of primes, until the
// sum goes past the largest possible prime. Store the
// last sum reached that _was_ a prime, and the number
// of primes involved.
for p := i; p > 0; p = numbers[p].previousPrimeIndex {
if !numbers[p].isPrime {
panic("wtf")
}
sum += p
numPrimesTried++
if sum > largestPrime {
// Don't try any more primes!
break
} else {
// Book keeping
if numbers[sum].isPrime {
lastPrimeSum = sum
numPrimesInSum = numPrimesTried
}
}
}
numbers[i].maxPrimeSum = lastPrimeSum
numbers[i].maxConsecutivePrimes = numPrimesInSum
// fmt.Println("max prime sum for ", i, " = ", numbers[i].maxPrimeSum)
}
}
func findMaxPrimeSum() {
// Use the pre-calculated primes sums to figure out the maximum and print some summary info
maxConsecutivePrimes := 0
maxPrimeSum := 0
for i := 0; i < MAX_NUM; i++ {
if numbers[i].isPrime {
if numbers[i].maxConsecutivePrimes > maxConsecutivePrimes {
maxConsecutivePrimes = numbers[i].maxConsecutivePrimes
maxPrimeSum = numbers[i].maxPrimeSum
fmt.Println("max prime sum = ", maxPrimeSum, ", with ", maxConsecutivePrimes, " primes, ending in ", i)
}
}
}
}
func main() {
numbers = make([]Number, MAX_NUM)
populatePrimes()
calculatePrimeSums()
findMaxPrimeSum()
}
The best part? It ran in 0.363 seconds!