概要

今回は、1<= X <=10^9 の範囲の自然数Xを渡されたとき、Xが素数か否かを判定します。

判定には、試し割り法を使いました。

コード

↓のようになりました

import scala.math.sqrt
object PrimeNum {
def main(args:Array[String]) {
val num:Long = args(0).toLong
if(isPrime(num)) println(num + " is Prime Number.")
else println(num + " is NOT Prime Number.")
}
def isPrime(num:Long):Boolean = {
if (num == 1 || num%2==0) {
false
} else {
(3L to sqrt(num).toLong).filter(
n => n%2 != 0
).foreach { e =>
if(num%e == 0) return false
}
true
}
}
view raw PrimeNum.scala hosted with ❤ by GitHub

解説

処理のおおまかな流れは以下のような感じ

  • 対象の数字Xを受け取る
  • Xが１か偶数だったら、素数ではない
  • 3からXの平方根までのリストを作る
  • リストから偶数を除去
  • リストの先頭から順に、Xがその数で割り切れるかどうかを調べる
  • 割り切れたら、素数ではない
  • 割り切れずに、リストの末尾まで到達したら、素数
  • 結果を表示

(x to y).filter().foreach() の形式で書きたかったのでこんな設計になりました。 なんとなくScalaっぽくてこの書き方が好きなので

foreachの中の処理で割り切れた場合、明示的なreturnでループを抜けています

対象の数が大きくなると生成されるリストも大きくなり、ループが長くなるので filterの条件を増やして(ex. 3, 5, 7, 11,,,)リストが短くなるようにしてみたりもしたんですが、 早くなりませんでした、というか若干遅くなった。。。

filterを追加することでループの回数を減らすことの損益分岐点は、思ったより低かったようです。無念

追記

@gakuzzzzさんにコメントいただき、コードを改良しました。

コード・その２

import scala.math.sqrt
object PrimeNum {
def main(args:Array[String]) {
val num:Long = args(0).toLong
if(isPrime(num)) println(num + " is Prime Number.")
else println(num + " is NOT Prime Number.")
}
def isPrime(num:Long):Boolean = {
if (num == 1 || num%2==0) {
false
} else {
(3L to sqrt(num).toLong by 2).foreach {
e => if(num%e == 0) return false
}
true
}
}
view raw PrimeNum.scala hosted with ❤ by GitHub

(x to y by 2)とすることで、2刻みでリストを生成するので、最初に生成されるリストが短くできる&filterが省略できるわけですね。

Before:140ms, After:130ms だいたい10msほど速くなりました。

コード・その３

import scala.math.sqrt
object PrimeNum {
def main(args:Array[String]) {
val num:Long = args(0).toLong
if(isPrime(num)) println(num + " is Prime Number.")
else println(num + " is NOT Prime Number.")
}
def isPrime(num:Long):Boolean = {
if (num == 1 || num%2==0) {
false
} else {
(3L to sqrt(num).toLong by 2).forall {
e => num%e != 0
}
}
}
view raw PrimeNum.scala hosted with ❤ by GitHub

returnを使うと例外で遅くなるのでは？という話もあったので、forallを使うパターンも試してみました。 結果は↑とほぼ同じ結果になりました。 forallがbooleanを返すので、returnのためのtrue/falseがなくなったので、コードはだいぶ綺麗になった気がします。