Project Euler Problem 1

Multiples of 3 or 5

Find the sum of all numbers below 1000 which have 3 or 5 as a factor (i.e. are divisible by those numbers with no remainder).

Solution

For such a small search space, we can simply iterate over all the numbers from 1 to 999, test whether they are divisible by 3 or 5, and keep a running total.

package main

import "fmt"

func main() {
    sum := 0

    for n := 1; n < 1000; n++ {
        if n%3 == 0 || n%5 == 0 {
            sum += n
        }
    }

    fmt.Println(sum)
}

If the search space was much larger, an alternative solution would be to start at 3 and add every 3rd number to a list, then do the same from 5 for every 5th number (excluding any numbers already in the list), then the sum of the list calculated. This would require more memory (to store the list elements), but most of the instructions used would be ADD, which takes fewer cycles than the DIV required by modulus (although an intelligent compiler might optimise division by a constant value to avoid DIV).