Scroll Top

EULER NO.5 : Smallest multiple

euler_portrait

Smallest multiple

1부터 20까지의 최소공배수를 구해야 한다.
최소공배수는 a * b / (a와 b의 최대공약수) 이다.

알고리즘은 유클리드 호제법을 사용했다.

package main
import (
        "fmt"
        "time"
)

func gcd(a, b int) int { // 최대공약수
        for b != 0{
                c := b
                b = a % b
                a = c
        }
        return a
}

func lcm(a, b int) int { // 최소공배수
        fmt.Println(a, "&", b)
        return a * b / gcd(a, b)
}

func main() {
        start := time.Now()
        var min, max int = 1, 20
        var result int = min
        for i:=2; i<=max; i++{
                result = lcm(i, result)
        }
        fmt.Println("최대공배수는 ", result)
        fmt.Println("계산 시간 : ", time.Since(start))
}
┌──(daleji㉿HACK)-[~]
└─$ go run euler5.go
2 & 1
3 & 2
4 & 6
5 & 12
6 & 60
7 & 60
8 & 420
9 & 840
10 & 2520
11 & 2520
12 & 27720
13 & 27720
14 & 360360
15 & 360360
16 & 360360
17 & 720720
18 & 12252240
19 & 12252240
20 & 232792560
최대공배수는  232792560
계산 시간 :  100.3µs

Leave a comment

You must be logged in to post a comment.