Project Euler Problem 7

Find the 10,001st prime number.

Solution

In Problem 3, we wrote a function to build the Sieve of Eratosthenes, which will find us all the prime numbers up to maxNumber:

func getPrimes(maxNumber int) []int {
	const UNKNOWN = 0
	const NOT_PRIME = 1
	const IS_PRIME = 2
	const FIRST_PRIME = 2

	primes := []int{}

	// Use make for the sieve because we know the size and everything should
	// be populated with zero
	sieve := make([]int, maxNumber+1)
	sieve[FIRST_PRIME] = IS_PRIME

	for sieveIndex, currentPrime := FIRST_PRIME, FIRST_PRIME; currentPrime != 0 && sieveIndex <= maxNumber; sieveIndex++ {
		// Assume this prime will be the last
		nextPrime := 0
		step := currentPrime

		// Mark all multiples of current prime as non-prime
		for j := currentPrime + step; j <= maxNumber; j += step {
			sieve[j] = NOT_PRIME
		}

		// Find the next unknown element after the current prime
		// This will be the next prime
		for k := currentPrime + 1; nextPrime == 0 && k <= maxNumber; k++ {
			if sieve[k] == UNKNOWN {
				sieve[k] = IS_PRIME
				nextPrime = k
			}
		}

		// Set current prime to be the next prime
		// If there is no next prime (nextPrime == 0), this will end
		// the for loop as currentPrime != 0 will be false
		currentPrime = nextPrime
	}

	// We now have a sieve with all the numbers flagged as prime/not prime
	// Extract just the primes and return as a slice
	for s := FIRST_PRIME; s <= maxNumber; s++ {
		if sieve[s] == IS_PRIME {
			primes = append(primes, s)
		}
	}

	return primes
}

This allowed us to find the highest prime number which is less than or equal to maxNumber, but it does not allow us to find the nth prime. To do this we would have to know roughly where the nth prime would appear, but this is difficult because primes are not evenly distributed (there are ways to estimate this, but the mathematics is beyond my skills).

However, given that we’re using a small value of n, we can guess that a prime will appear every x numbers, and then increase x if we don’t find the nth prime in the sieve. Let’s use a very simple rule of assuming there is one prime for every ten numbers, and then double it each time, i.e.

1 prime for every 10 numbers
1 prime for every 20 numbers
1 prime for every 40 numbers

We can print the prime density on each iteration so that know it is working.

First we need another simple function to find the nth element in a slice, which just involves checking that the slice contains at least n elements (slices are zero-indexed, so the nth element will actually be element n-1, but the length will be n). It returns the nth prime value and a boolean flag for whether the nth prime exists (if it doesn’t, the value returned is meaningless, but we set to zero).

func findPrimeN(n int, primeDensity int) (int, bool) {
	primes := getPrimes(n * primeDensity)

	if len(primes) >= n {
		return primes[n-1], true
	} else {
		return 0, false
	}
}

Note that unlike PHP, where we can use isset($primes[$n-1]), in Go we have to check the length of the slice. This is fine as Go does not support sparse slices, i.e. we cannot have a slice where s[0] and s[2] exist without s[1] existing.

Now we can call findPrimeN with an increasing prime density:

func main() {
	const N = 10001

	for primeN, primeDensity, primeFound := 0, 10, false; !primeFound; primeDensity *= 2 {
		fmt.Println("primeDensity: " + strconv.Itoa(primeDensity))
		primeN, primeFound = findPrimeN(N, primeDensity)

		if primeFound {
			fmt.Println("Prime " + strconv.Itoa(N) + " = " + strconv.Itoa(primeN))
		}
	}
}

One final gotcha - the initial version of this code was:

func main() {
	const N = 10001

	for primeDensity, primeFound := 10, false; !primeFound; primeDensity *= 2 {
		fmt.Println("primeDensity: " + strconv.Itoa(primeDensity))
		primeN, primeFound := findPrimeN(N, primeDensity)

		if primeFound {
			fmt.Println("Prime " + strconv.Itoa(N) + " = " + strconv.Itoa(primeN))
		}
	}
}

This would run indefinitely, or at least until the process ran out of memory when creating a slice with a huge primeDensity value. Can you see why? This line is the problem:

primeN, primeFound := findPrimeN(N, primeDensity)

This would create new variables, primeN and primeFound, because we’ve used the := operator. However, this means that primeFound is now a different variable to the one used to check whether the for loop should end with !primeFound. So the loop will never end! We can’t fix this by a simple switch to =:

primeN, primeFound = findPrimeN(N, primeDensity)

because the primeN variable does not exist. The easiest solution is to create a primeN variable in the for loop initialiser. Both primeN and primeFound exist and therefore can be assigned using =.