I ended up working so hard trying to get my benchmark time down that I ended up solving the problem in under 2 seconds without even knowing it!
This problem was easier since I had recently completed one that re-reminded me of the Sieve of Eratosthenes. I thought about it here too and it worked out really well in just counting the number of prime divisors. I think the code is a bit hard to read though so if this wasn’t just a one off program, I’d probably try to clean it up a bit and make it more readable. It was fun though trying to micro optimize it all though.
package main
import (
"fmt"
)
func sieve(max int) [][3]int {
sieve := make([][3]int, max+1)
for i := 2; i <= max; i++ {
if sieve[i][0] > 0 {
continue
}
for j := i; j <= max; j += i {
if sieve[j][0] == 0 {
sieve[j][0] = i
} else if sieve[j][1] == 0 {
sieve[j][1] = i
} else {
sieve[j][2] = i
}
}
}
return sieve
}
func S(N int) int {
divs := sieve(N)
dist := make(map[[3]int]int)
for num := 6; num <= N; num++ {
a := divs[num][0]
b := divs[num][1]
c := divs[num][2]
if a == 0 || b == 0 || c != 0 {
continue
}
dist[divs[num]] = num
}
var total int
for _, val := range dist {
total += val
}
return total
}
func main() {
answer := S(10000000)
fmt.Printf("answer: %#v\n", answer)
}
package main
import (
"testing"
)
func TestS(t *testing.T) {
if act := S(100); act != 2262 {
t.Error("Incorrect value for S(100):", act)
}
}
var result int
func BenchmarkS(b *testing.B) {
var a int
for n := 0; n < b.N; n++ {
a = S(100)
}
result = a
}