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
