home
>
Project Euler
>
ForNext
Shut the fuck up and write some code
Problem 7
10001番目の素数
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.
10001st prime
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
VBScript
JScript
Perl
PHP
Python
Ruby
PowerShell
Scala
更新日 : 2013.01.21
まず、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
F#
更新日 : 2013.01.21
> exception WhileBreak of unit;;
exception WhileBreak of unit
> let mutable prime_list = [2];;
val mutable prime_list : int list = [2]
> let mutable cnt = 1;;
val mutable cnt : int = 1
> let mutable num = 3;;
val mutable num : int = 3
>
- while (cnt < 10001) do
- let num_sqrt = sqrt (float num)
- let mutable fPrime = true
- try
- prime_list
- |> List.iter (fun p ->
- if ((float p) > num_sqrt) then
- raise (WhileBreak ())
- elif (num % p = 0) then
- fPrime <- false
- raise (WhileBreak ())
- )
- with _ -> ()
-
- if fPrime then
- prime_list <- List.append prime_list [num]
- cnt <- cnt + 1
- num <- num + 2
- ;;
|> List.iter (fun p ->
----------------------^
stdin(11,23): error FS0407: The mutable variable 'fPrime' is used in an invalid way. Mutable variables cannot be captured by closures. Consider eliminating this use of mutation or using a heap-allocated mutable reference cell via 'ref' and '!'.
クロージャになっちゃってるのか？
> exception WhileBreak of unit;; exception WhileBreak of unit > let mutable prime_list = [2];; val mutable prime_list : int list = [2] > let mutable cnt = 1;; val mutable cnt : int = 1 > let mutable num = 3;; val mutable num : int = 3 > let mutable fPrime = true;; val mutable fPrime : bool = true > - while (cnt < 10001) do - let num_sqrt = sqrt (float num) - fPrime <- true - try - prime_list - |> List.iter (fun p -> - if ((float p) > num_sqrt) then - raise (WhileBreak ()) - elif (num % p = 0) then - fPrime <- false - raise (WhileBreak ()) - ) - with _ -> () - - if fPrime then - prime_list <- List.append prime_list [num] - cnt <- cnt + 1 - num <- num + 2 - ;; val it : unit = () > prime_list.[prime_list.Length-1];; val it : int = 104743 > ;;
Scala版 より高速！