home
>
Project Euler
>
ForNext
Shut the fuck up and write some code
Problem 10
素数の和
10以下の素数の和は である.
200万以下の全ての素数の和を求めよ.
Summation of primes
The sum of the primes below 10 isFind the sum of all the primes below two million.
VBScript
JScript
Perl
PHP
Python
Ruby
PowerShell
Scala
更新日 : 2013.01.24
Problem 7 を 流用
scala> var prime_list = List(3)
prime_list: List[Int] = List(3)
scala> var num = 5
num: Int = 5
scala>
scala> while (num < 2000000) {
| 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)
| }
| num += 2
| }
warning: there were 1 deprecation warnings; re-run with -deprecation for details
scala> prime_list.last
res6: Int = 1999993
scala> prime_list = 2::prime_list
prime_list: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 94...
scala> prime_list.sum
res7: Int = 1179908154
いやになるほど遅いので、素直に奇数で試し割り
scala> var prime_sum = 2 + 3
prime_sum: Int = 5
scala> var num = 5
num: Int = 5
scala> while (num < 2000000) {
| var num_sqrt = Math.sqrt(num)
| var odd_num = 3
| var fPrime = true
| var fWhile = true
| while (fWhile) {
| if (odd_num > num_sqrt) {
| fWhile = false
| } else if (num % odd_num == 0) {
| fWhile = false
| fPrime = false
| } else odd_num += 2
| }
| if (fPrime) {
| prime_sum += num
| }
| num += 2
| }
warning: there were 1 deprecation warnings; re-run with -deprecation for details
scala> prime_sum
res3: Int = 1179908154
って言われちゃったよ...
もしかして桁あふれ？
scala> var prime_sum = 2L + 3L
prime_sum: Long = 5
scala> var num = 5L
num: Long = 5
scala> while (num < 2000000L) {
| var num_sqrt = Math.sqrt(num)
| var odd_num = 3L
| var fPrime = true
| var fWhile = true
| while (fWhile) {
| if (odd_num > num_sqrt) {
| fWhile = false
| } else if (num % odd_num == 0) {
| fWhile = false
| fPrime = false
| } else odd_num += 2
| }
| if (fPrime) {
| prime_sum += num
| }
| num += 2
| }
warning: there were 1 deprecation warnings; re-run with -deprecation for details
scala> prime_sum
res5: Long = 142913828922
F#
更新日 : 2013.01.24
> prime_sum;; val it : int = 5 > let mutable prime_sum = 2 + 3;; val mutable prime_sum : int = 5 > let mutable num = 5;; val mutable num : int = 5 > let mutable fPrime = true;; val mutable fPrime : bool = true > let mutable fWhile = true;; val mutable fWhile : bool = true > - while (num < 2000000) do - let num_sqrt = sqrt (float num) - let mutable odd_num = 3 - fPrime <- true - fWhile <- true - while (fWhile) do - if odd_num > (int num_sqrt) then - fWhile <- false - elif num % odd_num = 0 then - fWhile <- false - fPrime <- false - else - odd_num <- odd_num + 2 - if fPrime then - prime_sum <- prime_sum + num - num <- num + 2 - ;; val it : unit = () > prime_sum;; val it : int = 1179908154
あいやー
> prime_sum;; val it : int64 = 5L > let mutable prime_sum = 2L + 3L;; val mutable prime_sum : int64 = 5L > let mutable num = 5L;; val mutable num : int64 = 5L > let mutable fPrime = true;; val mutable fPrime : bool = true > let mutable fWhile = true;; val mutable fWhile : bool = true > - while (num < 2000000L) do - let num_sqrt = sqrt (float num) - let mutable odd_num = 3L - fPrime <- true - fWhile <- true - while (fWhile) do - if odd_num > (int64 num_sqrt) then - fWhile <- false - elif num % odd_num = 0L then - fWhile <- false - fPrime <- false - else - odd_num <- odd_num + 2L - if fPrime then - prime_sum <- prime_sum + num - num <- num + 2L - ;; val it : unit = () > prime_sum;; val it : int64 = 142913828922L