search
LoginSignup
3

More than 3 years have passed since last update.

posted at

updated at

Organization

Goでの素数判定と時間計測

はじめに

Go初心者なので生温かい目で読んで頂ければと思います。
Goの練習として、素数判定のアルゴリズムを書き、時間計測する。
アルゴリズムは2通り。時間計測はtimeパッケージを使う。
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())
}

実行

標準入力から97, 997, 9973で試します。

$ 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の方法)が速いのが明らかになっています。:clap:

これで終わりとなりますが、またの機会に、別の言語(Pythonとか)との速度比較などしてみたいですね。

参考

素数表
素数判定いろいろ

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
3