[Golang] Amicable Numbers - Problem 21 - Project Euler

2 years ago

source link: http://siongui.github.io/2017/05/25/go-amicable-numbers-problem-21-project-euler/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

[Golang] Amicable Numbers - Problem 21 - Project Euler

May 25, 2017

Go solution to amicable numbers - Problem 21 - Project Euler. [1]

Problem:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Solution:

[220 284 1184 1210 2620 2924 5020 5564 6232 6368]

31626

Run Code on Go Playground

package main

import (
      "fmt"
)

// Get all prime factors of a given number n
func PrimeFactors(n int) (pfs []int) {
      // Get the number of 2s that divide n
      for n%2 == 0 {
              pfs = append(pfs, 2)
              n = n / 2
      }

      // n must be odd at this point. so we can skip one element
      // (note i = i + 2)
      for i := 3; i*i <= n; i = i + 2 {
              // while i divides n, append i and divide n
              for n%i == 0 {
                      pfs = append(pfs, i)
                      n = n / i
              }
      }

      // This condition is to handle the case when n is a prime number
      // greater than 2
      if n > 2 {
              pfs = append(pfs, n)
      }

      return
}

// return p^i
func Power(p, i int) int {
      result := 1
      for j := 0; j < i; j++ {
              result *= p
      }
      return result
}

// formula comes from https://math.stackexchange.com/a/22723
func SumOfProperDivisors(n int) int {
      pfs := PrimeFactors(n)

      // key: prime
      // value: prime exponents
      m := make(map[int]int)
      for _, prime := range pfs {
              _, ok := m[prime]
              if ok {
                      m[prime] += 1
              } else {
                      m[prime] = 1
              }
      }

      sumOfAllFactors := 1
      for prime, exponents := range m {
              sumOfAllFactors *= (Power(prime, exponents+1) - 1) / (prime - 1)
      }
      return sumOfAllFactors - n
}

func AmicableNumbersUnder10000() (amicables []int) {
      for i := 3; i < 10000; i++ {
              s := SumOfProperDivisors(i)
              if s == i {
                      continue
              }
              if SumOfProperDivisors(s) == i {
                      amicables = append(amicables, i)
              }
      }
      return
}

func main() {
      amicables := AmicableNumbersUnder10000()
      fmt.Println(amicables)

      sum := 0
      for i := 0; i < len(amicables); i++ {
              sum += amicables[i]
      }
      fmt.Println(sum)
}

The method for sum of all proper divisors (factors) comes from my another post [2].

References:

Recommend