euler 50 consecutive prime sum

May 29, 2015  

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!