package main

import (
	"fmt"
	"time"
)

type number struct {
	n int
	d int
	s []int
}

func newNumber(x int) *number {
	if x <= 1 {
		return &number{n: 0, d: 0}
	}
	return &number{n: x, d: x}
}

func (n *number) div(p int) {
	if n.d%p == 0 {
		for n.d%p == 0 {
			n.d /= p
		}
		n.s = append(n.s, p)
	}
}

func (x number) phi() (answer int64) {
	if x.n <= 1 {
		return 0
	}
	if x.n == x.d {
		return int64(x.n) - 1
	}
	ratio := [2]int64{int64(x.n), 1}
	for i := range x.s {
		p := int64(x.s[i])
		ratio[0] *= p - 1
		ratio[1] *= p
	}
	return ratio[0] / ratio[1]
}

type numbers []*number

func newNumbers(max int) (answer numbers) {
	answer = make(numbers, max+1)
	for i := range answer {
		answer[i] = newNumber(i)
	}
	for p := 2; 2*p <= max; p++ {
		if answer[p].n == answer[p].d {
			for i := 2; p*i <= max; i++ {
				answer[p*i].div(p)
			}
		}
	}
	return
}

func problem72() (answer int64) {
	xs := newNumbers(1000000)
	for i := range xs {
		answer += int64(xs[i].phi())
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem72())
	end := time.Now()
	fmt.Println(end.Sub(start).Seconds())
}