1
\$\begingroup\$

I've been working on Project Euler, here was my solution for Problem #1. It gave me the proper answer, but it's egregiously slow. How can I implement this more efficiently? My math skills aren't top-notch, sorry.

package main

import (
    "fmt"
)

// Problem1: find the sum of all the multiples of 3 or 5 below 1000.
// x,y: multiples
// z: upper limit
func Problem1(x, y, z int) int {

    Multiples := make(map[int]struct{})

    var Sum int
    for i := 1; i < z; i++ {
        XFactor := x * i
        YFactor := y * i

        if XFactor < z {
            Multiples[XFactor] = struct{}{}
        }
        if YFactor < z {
            Multiples[YFactor] = struct{}{}
        }
    }

    for key, _ := range Multiples {
        Sum = Sum + key
    }

    return Sum
}

func main() {
    fmt.Println("The answer to problem 1 is: ", Problem1(3,5,1000))
}

Thanks! https://play.golang.org/p/MQLpjtMvmw

\$\endgroup\$
  • 1
    \$\begingroup\$ Project Euler is not about implementation, but all about algorithm, if algebra-heavy. (And why does it read answer to problem 2?) \$\endgroup\$ – greybeard Sep 2 '16 at 4:42
  • \$\begingroup\$ Yeah, that's partly what I'm hoping to learn about! I copied it from the wrong line in my program, I fixed it :) \$\endgroup\$ – mxplusb Sep 2 '16 at 6:01
  • \$\begingroup\$ Lookup any PE #1 question here on CR, and you'll find the closed-form solution (which does not require iteration at all). \$\endgroup\$ – Martin R Sep 2 '16 at 6:28
4
\$\begingroup\$

Closed form solution

The problem is basically a sum over an arithmetic sequence, which has the well defined solution (first + last) * count / 2

func ArithmeticSum(first, step, count int) int {
    var last int = first + step * (count - 1);
    return (first + last) * count / 2;
}

The only difficulty arises from the requirement to sum numbers that are a multiple of both x and y just once. The easiest way to achieve this is to sum x and y independently and subtract the common multiples.

func Problem1(x, y, z int) int {
    var sumX int = ArithmeticSum(0, x, (z - 1) / x + 1);
    var sumY int = ArithmeticSum(0, y, (z - 1) / y + 1);
    var lcm int = Lcm(x, y);
    var sumBoth int = ArithmeticSum(0, lcm, (z - 1) / lcm + 1);
    return sumX + sumY - sumBoth;
}

Luckily, the common multiples also form an arithmetic series. It's step is the least common multiple of x and y.

func Lcm(a, b int) int {
    return a * b  / Gcd(a, b);
}

The least common multiple can be calculated from the greatest common divisor, which itself can be found via Euclid's algorithm.

func Gcd(a, b int) int {
    if b == 0 {
        return a;
    } else {
        return Gcd(b, a % b);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Ah, cool! These problems are definitely teaching me about a lot of math I've either not used in years or teaching me new algorithms. Thanks! \$\endgroup\$ – mxplusb Sep 3 '16 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.