Project Eulerに挑戦: 問題5

Table of Contents

問題5

1から20のすべてで割り切れる最小の整数を求めよ.

Cで解く

1から20のLCM (最小公倍数)を求めれば良い. aとbのLCMは,aとbのGCD (最大公約数)をgとすれば a*b/g で求められる.

aとbのGCDを求めるにはユークリッドの互除法(Euclidean algorithm)を用いる. ユークリッドの互除法により,GCDは以下のように再帰的に定義できる.

  • GCD(a, 0) = a
  • GCD(a, b) = GCD(b, a mod b) (if b > 0)

プログラムは以下のようになる(64ビット整数を用いている).

 1:  long long gcd(long long a, long long b) {
 2:      if (b == 0)
 3:          return a;
 4:      return gcd(b, a % b);
 5:  }
 6:  
 7:  long long lcm(long long a, long long b) {
 8:      return a * b / gcd(a, b);
 9:  }
10:  
11:  long long e005() {
12:      long long i;
13:      long long n = 1;
14:      for (i = 1; i <= 20; i++) {
15:          n = lcm(n, i);
16:      }
17:      return n;
18:  }

Scalaで解く

GCDおよびLCMを求める関数を定義する.

1:  def gcd(a: Long, b: Long): Long =
2:    if (b == 0) a else gcd(b, a % b)
3:  def lcm(a: Long, b: Long): Long =
4:    a * b / gcd(a, b)

したがって回答は以下で求められる.

scala> (1L to 20L).reduceLeft(lcm(_, _))

手で解く

20以下で,各素数のベキ乗の最大値は以下のようになる.

素数ベキ乗
224
332
551
771
11111
13131
17171
19191

それらの積 24*32*5*7*11*13*17*19 が回答である.

Date: 2017-09-29 21:44:25 JST

Author: 田村直之

Validate XHTML 1.0