Go의 소수 판정 및 시간 측정

7640 단어 Go

입문


고 초보자니까 따뜻한 눈으로 읽었으면 좋겠어요.
Go의 연습으로 소수 판정 알고리즘을 쓰고 시간을 측정한다.
알고리즘은 두 가지가 있다.시간 측정은 타임 패키지를 사용합니다.
1. 정수 x에 대해 2부터 x-1까지의 순서에 따라 제거할 수 있는지 여부를 판정한다.
2. 정수 x에 대해 먼저 짝수를 판정하고 3에서 ≠x로 순서대로 2를 증가하며 제거할 수 있는지 여부를 판정한다.

환경


Go 1.11.2

출처


prime.go
package main

import (
    "fmt"
    "math"
    "time"
)

func isPrime(x int) bool {
    if x == 1 {
        return false
    }
    if x == 2 {
        return true
    }

    b := true
    for i := 2; i < x; i++ {
        if x%i == 0 {
            b = false
            break
        }
    }
    return b
}

func isPrime2(x int) bool {
    if x == 1 {
        return false
    }
    if x == 2 {
        return true
    }
    if x%2 == 0 {
        return false
    }

    b := true
    rootx := int(math.Sqrt(float64(x)))
    i := 3
    for i <= rootx {
        if x%i == 0 {
            b = false
            break
        }
        i += 2
    }
    return b
}

func main() {
    var i int
    // 標準入力を代入
    fmt.Scan(&i)

    start := time.Now()
    b := isPrime(i)
    end := time.Now()
    fmt.Println(b)
    fmt.Printf("%f秒\n", (end.Sub(start)).Seconds())

    start = time.Now()
    b = isPrime2(i)
    end = time.Now()
    fmt.Println(b)
    fmt.Printf("%f秒\n", (end.Sub(start)).Seconds())
}

실행


표준 입력에서 97997973으로 시도합니다.
$ go run prime.go
97
true
0.000004秒
true
0.000000秒
$ go run prime.go
997
true
0.000030秒
true
0.000001秒
$ go run prime.go
9973
true
0.000380秒
true
0.000002秒
큰 수량일수록 isPrime2(2의 방법)가 빠르다
여기서 마치겠습니다. 다음에 기회가 있으면 다른 언어(Python 등)와 속도를 비교하고 싶습니다.

참고 자료


질량계
질수는 각양각색을 판정한다

좋은 웹페이지 즐겨찾기