515hikaru
4/7/2018 - 2:59 PM

gcd.go

package main

import (
	"fmt"
)

const n = 1000

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func main() {
	c := 0
	for i := 1; i < n; i++ {
		c = 0
		for j := 1; j < i; j++ {
			if gcd(i, j) == 1 {
				c++
			}
		}
		fmt.Println(i, c)
	}
}