こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

素数判定 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

最初は以下のように実装しました。

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    if n == 1 {
        fmt.Println("NO")
        return
    }
    for i := 2; i < n; i++ {
        if n % i == 0 {
            fmt.Println("NO")
            return
        }
    }
    fmt.Println("YES")
}

（ほんとの最初はn = 1のときの考慮もなかったことは内緒）

ですが当然のように実行時間オーバーしてしまいました。

残念。。

ということで解説を見ると…目から鱗な解決法がありました。

実は調べるのは Nの0.5乗（ルートN） まででいいです。 なぜかというと、 N に 1 と N 以外の約数があると仮定した場合、少なくとも 1 つは N の 0.5 乗（ルート N ） 以下の約数があることになるからです。

ということで実装を変更します。

なんと先ほどのコードに2文字追加するだけで解決できてしまいます。

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    if n == 1 {
        fmt.Println("NO")
        return
    }
    // 条件式をi*i < nとするだけでOK
    for i := 2; i*i < n; i++ {
        if n % i == 0 {
            fmt.Println("NO")
            return
        }
    }
    fmt.Println("YES")
}

いやぁびっくりしました。確かに言われてみればという方法でした。

ということで今回はこれで👍