// Find all primes <= n
func SieveOfEratosthenes(n int) []int {
      // Create a boolean array "prime[0..n]" and initialize
      // all entries it as true. A value in prime[i] will
      // finally be false if i is Not a prime, else true.
      integers := make([]bool, n+1)
      for i := 2; i < n+1; i++ {
              integers[i] = true
      }

      for p := 2; p*p <= n; p++ {
              // If integers[p] is not changed, then it is a prime
              if integers[p] == true {
                      // Update all multiples of p
                      for i := p * 2; i <= n; i += p {
                              integers[i] = false
                      }
              }
      }

      // return all prime numbers <= n
      var primes []int
      for p := 2; p <= n; p++ {
              if integers[p] == true {
                      primes = append(primes, p)
              }
      }

      return primes
}

// Given a positive even integer n,
// return the two primes that sum up to n.
func Goldbach(n int) (p1, p2 int) {
      if n < 3 {
              return
      }
      if n%2 == 1 {
              return
      }

      primes := SieveOfEratosthenes(n)

      m := make(map[int]bool)
      for i := 0; i < len(primes); i++ {
              m[primes[i]] = true
      }

      for p, _ := range m {
              if _, ok := m[n-p]; ok {
                      p1 = p
                      p2 = n - p
                      return
              }
      }
      return
}