Project Euler #1 in Go (counting multiples of 3 or 5 up to 1000)

Question

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

Answer 1

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);
    }
}