Scala で Project Euler Problem 7
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.
What is the 10 001st prime number?
まず、20未満の素数を求めてみる
scala> var prime_list = List(2) prime_list: List[Int] = List(2) scala> for (no <- 3 to 20 by 2) { | var i = 0 | var j = 0 | var f = true | while (f) { | if (prime_list(i) * prime_list(i) > no) { | f = false | } else if (no % prime_list(i) == 0) { | j = 1 | f = false | } else i += 1 | } | if (j == 0) prime_list = prime_list:::List(no) | } scala> prime_list res1: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19) scala> prime_list.last res2: Int = 19 scala>
次に、素数を20個 求めてみる
scala> var prime_list = List(2) prime_list: List[Int] = List(2) scala> var no = 3 no: Int = 3 scala> while (prime_list.length < 20) { | var i = 0 | var j = 0 | var f = true | while (f) { | if (prime_list(i) * prime_list(i) > no) { | f = false | } else if (no % prime_list(i) == 0) { | j = 1 | f = false | } else i += 1 | } | if (j == 0) prime_list = prime_list:::List(no) | no += 2 | } scala> prime_list res4: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71) scala> prime_list.last res5: Int = 71 scala>
素数を10001個 求める
scala> var prime_list = List(2) prime_list: List[Int] = List(2) scala> var no = 3 no: Int = 3 scala> while (prime_list.length < 10001) { | var i = 0 | var j = 0 | var f = true | while (f) { | if (prime_list(i) * prime_list(i) > no) { | f = false | } else if (no % prime_list(i) == 0) { | j = 1 | f = false | } else i += 1 | } | if (j == 0) prime_list = prime_list:::List(no) | no += 2 | } scala> prime_list.last res7: Int = 104743 scala>
かなり時間がかかった
prime_list:::List(no) が時間を食ってるんじゃないかという事で、ちょいと変更
scala> var prime_list = List(2) prime_list: List[Int] = List(2) scala> var no = 3 no: Int = 3 scala> while (prime_list.length < 10001) { | var i = prime_list.length - 1 | var j = 0 | var f = true | while (f) { | if (prime_list(i) * prime_list(i) > no) { | f = false | } else if (no % prime_list(i) == 0) { | j = 1 | f = false | } else i -= 1 | } | if (j == 0) prime_list = no::prime_list | no += 2 | } scala> prime_list.head res9: Int = 104743
めちゃくちゃ、遅くなってしまった...
素数が見つかるたびに、素数表に追加して行き、素数かどうかの判定は、その素数表の数で割ってみる
という方針をやめて、素数表は作らず、素数かどうかの判定は、単に片っ端から奇数で割ってみる
scala> var max_prime = 2 max_prime: Int = 2 scala> var cnt = 1 cnt: Int = 1 scala> var no = 3 no: Int = 3 scala> while (cnt < 10001) { | var fWhile = true | var fPrime = true | var i = 3 | var j = Math.sqrt(no) | while (fWhile) { | if (i > j) { | fWhile = false | } else if (no % i == 0) { | fWhile = false | fPrime = false | } else i += 2 | } | if (fPrime) { | max_prime = no | cnt += 1 | } | no += 2 | } warning: there were 1 deprecation warnings; re-run with -deprecation for details scala> max_prime res10: Int = 104743
こっちの方が、よっぽど速かった。
でも、こんなのは邪道
scala> var prime_list = List(2) prime_list: List[Int] = List(2) scala> var cnt = 1 cnt: Int = 1 scala> var num = 3 num: Int = 3 scala> scala> while (cnt < 10001) { | var num_sqrt = Math.sqrt(num) | | var work_list = prime_list.reverse | var p = work_list.head | | var fPrime = true | var fWhile = true | while (fWhile) { | if (p > num_sqrt) { | fWhile = false | } else if (num % p == 0) { | fPrime = false | fWhile = false | } else { | work_list = work_list.tail | p = work_list.head | } | } | | if (fPrime) { | prime_list = num::prime_list | cnt += 1 | } | num += 2 | } warning: there were 1 deprecation warnings; re-run with -deprecation for details scala> prime_list.head res1: Int = 104743
やはり、時間がかかる
scala> var prime_list = List(2) prime_list: List[Int] = List(2) scala> var cnt = 1 cnt: Int = 1 scala> var num = 3 num: Int = 3 scala> scala> while (cnt < 10001) { | var num_sqrt = Math.sqrt(num) | | var work_list = prime_list | var p = work_list.head | | var fPrime = true | var fWhile = true | while (fWhile) { | if (p > num_sqrt) { | fWhile = false | } else if (num % p == 0) { | fPrime = false | fWhile = false | } else { | work_list = work_list.tail | p = work_list.head | } | } | | if (fPrime) { | prime_list = prime_list:::List(num) | cnt += 1 | } | num += 2 | } warning: there were 1 deprecation warnings; re-run with -deprecation for details scala> prime_list.last res9: Int = 104743
こっちのが、まし
もうちょっとだけ、Scala らしく...
scala> var prime_list = List(2) prime_list: List[Int] = List(2) scala> var cnt = 1 cnt: Int = 1 scala> var num = 3 num: Int = 3 scala> scala> while (cnt < 10001) { | var num_sqrt = Math.sqrt(num) | var fPrime = true | scala.util.control.Breaks.breakable { | prime_list.foreach { p => | if (p > num_sqrt) { | scala.util.control.Breaks.break | } else if (num % p == 0) { | fPrime = false | scala.util.control.Breaks.break | } | } | } | | if (fPrime) { | prime_list = prime_list:::List(num) | cnt += 1 | } | num += 2 | } warning: there were 1 deprecation warnings; re-run with -deprecation for details scala> prime_list.last res19: Int = 104743