Scala で Project Euler Problem 12
28の約数を列挙してみる
scala> var factor_list:List[Int] = List(1, 28) factor_list: List[Int] = List(1, 28) scala> for (i <- 2 to 28 / 2) { | if (28 % i == 0) { | factor_list = i::factor_list | println(i) | } | } 2 4 7 14 scala> factor_list res1: List[Int] = List(14, 7, 4, 2, 1, 28)
約数のリストを返す関数
scala> def get_factor_list(n:Int) = { | var factor_list = List(1) | for (i <- 2 to n / 2) { | if (n % i == 0) { | factor_list = i::factor_list | } | } | if (n != 1) n::factor_list else factor_list | } get_factor_list: (n: Int)List[Int] scala> get_factor_list(1) res2: List[Int] = List(1) scala> for (n <- 1 to 10) { | print(n + ":") | get_factor_list(n * (n + 1) / 2).foreach(i => print(i + ",")) | println | } 1:1, 2:3,1, 3:6,3,2,1, 4:10,5,2,1, 5:15,5,3,1, 6:21,7,3,1, 7:28,14,7,4,2,1, 8:36,18,12,9,6,4,3,2,1, 9:45,15,9,5,3,1, 10:55,11,5,1,
約数の数を返す関数
scala> def get_factor_cnt(n:Int) = { | var factor_cnt = 1 | for (i <- 2 to n / 2) { | if (n % i == 0) { | factor_cnt += 1 | } | } | if (n != 1) factor_cnt += 1 | factor_cnt | } get_factor_cnt: (n: Int)Int scala> get_factor_cnt(1) res4: Int = 1 scala> for (n <- 1 to 10) { | val triangular_num = n * (n + 1) / 2 | println(n + ":" + triangular_num + "->" + get_factor_cnt(triangular_num)) | } 1:1->1 2:3->2 3:6->4 4:10->4 5:15->4 6:21->4 7:28->6 8:36->9 9:45->6 10:55->4
scala> var n = 1 n: Int = 1 scala> var fWhile = true fWhile: Boolean = true scala> while (fWhile) { | val triangular_num = n * (n + 1) / 2 | println(n + ":" + triangular_num + "->" + get_factor_cnt(triangular_num)) | if (n > 10) fWhile = false else n += 1 | } 1:1->1 2:3->2 3:6->4 4:10->4 5:15->4 6:21->4 7:28->6 8:36->9 9:45->6 10:55->4 11:66->8
約数の数が10を超える最初の三角数
scala> var n = 1 n: Int = 1 scala> var fWhile = true fWhile: Boolean = true scala> while (fWhile) { | val triangular_num = n * (n + 1) / 2 | val factor_cnt = get_factor_cnt(triangular_num) | println(n + ":" + triangular_num + "->" + factor_cnt) | if (factor_cnt > 10) fWhile = false else n += 1 | } 1:1->1 2:3->2 3:6->4 4:10->4 5:15->4 6:21->4 7:28->6 8:36->9 9:45->6 10:55->4 11:66->8 12:78->8 13:91->4 14:105->8 15:120->16
約数の数が100を超える最初の三角数
scala> var n = 1 n: Int = 1 scala> var fWhile = true fWhile: Boolean = true scala> while (fWhile) { | val triangular_num = n * (n + 1) / 2 | val factor_cnt = get_factor_cnt(triangular_num) | if (factor_cnt > 100) { | println(n + ":" + triangular_num + "->" + factor_cnt) | fWhile = false | } else n += 1 | } 384:73920->112
約数の数が200を超える最初の三角数
scala> var n = 1 n: Int = 1 scala> var fWhile = true fWhile: Boolean = true scala> while (fWhile) { | val triangular_num = n * (n + 1) / 2 | val factor_cnt = get_factor_cnt(triangular_num) | if (factor_cnt > 200) { | println(n + ":" + triangular_num + "->" + factor_cnt) | fWhile = false | } else n += 1 | } 2015:2031120->240
約数の数が300を超える最初の三角数
scala> var n = 1 n: Int = 1 scala> var fWhile = true fWhile: Boolean = true scala> while (fWhile) { | val triangular_num = n * (n + 1) / 2 | val factor_cnt = get_factor_cnt(triangular_num) | if (factor_cnt > 300) { | println(n + ":" + triangular_num + "->" + factor_cnt) | fWhile = false | } else n += 1 | } 2079:2162160->320
遅すぎて使い物にならんので、別の手を考える
まず、素因数分解
scala> def get_prime_factor_list(n: Long, factor: Long = 2): List[Long] = { | if (n < factor * factor) List(n) | else if (n % factor != 0 ) get_prime_factor_list(n , factor + 1) | else factor::get_prime_factor_list(n / factor, factor ) | } get_prime_factor_list: (n: Long,factor: Long)List[Long] scala> get_prime_factor_list(73920) res11: List[Long] = List(2, 2, 2, 2, 2, 2, 3, 5, 7, 11) scala> val prime_factor_list = get_prime_factor_list(73920) prime_factor_list: List[Long] = List(2, 2, 2, 2, 2, 2, 3, 5, 7, 11) scala> val prime_factor_list = get_prime_factor_list(28) prime_factor_list: List[Long] = List(2, 2, 7)
それぞれの素因数の 次数+1 を取得
scala> var exp_list:List[Long] = List() exp_list: List[Long] = List() scala> var exp = 0L exp: Long = 0 scala> var factor = prime_factor_list(0) factor: Long = 2 scala> prime_factor_list.foreach { n => | if (n == factor) exp += 1 | else { | if (exp != 0) exp_list = (exp + 1)::exp_list | factor = n | exp = 1 | } | } scala> exp_list = (exp + 1)::exp_list exp_list: List[Long] = List(2, 3) scala> exp_list res13: List[Long] = List(2, 3)
それぞれの素因数の 次数+1 の 総積 が 約数の数
scala> exp_list.reduceLeft(_*_) res14: Long = 6
約数の数を返す関数を作り直す
scala> def get_factor_cnt2(n:Int) = { | val prime_factor_list = get_prime_factor_list(n) | var exp_list:List[Long] = List() | var exp = 0L | var factor = prime_factor_list(0) | prime_factor_list.foreach { n => | if (n == factor) exp += 1 | else { | if (exp != 0) exp_list = (exp + 1)::exp_list | factor = n | exp = 1 | } | } | exp_list = (exp + 1)::exp_list | exp_list.reduceLeft(_*_) | } get_factor_cnt2: (n: Int)Long scala> get_factor_cnt2(73920) res15: Long = 112
約数の数が500を超える最初の三角数
scala> var n = 1 n: Int = 1 scala> var m = 500 m: Int = 500 scala> var fWhile = true fWhile: Boolean = true scala> while (fWhile) { | val triangular_num = n * (n + 1) / 2 | val factor_cnt = get_factor_cnt2(triangular_num) | | if (factor_cnt > m) { | println(n + ":" + triangular_num + "->" + factor_cnt) | fWhile = false | } else n += 1 | } 12375:76576500->576