高校数学１０分プログラミング（43日目、2024年7月31日）

おはようございます。

今日は、高校数学１０分プログラミングの43日目です。

本日の課題は、一昨日と昨日作成した最大公約数や最小公倍数を計算するプログラムを関数化することです。

課題

整数$${M}$$と$${N}$$の最大公約数を求める関数 getGCD や整数$${M}$$と$${N}$$の最小公倍数を求める関数 getLCM を作成した上で、$${M=12}$$と$${N=30}$$の最大公約数や最小公倍数を求め、コンソールに出力するプログラムを作成してください。
なお、整数$${M}$$と$${N}$$の最大公約数を求める関数 getGCD と整数$${M}$$と$${N}$$の最小公倍数を求める関数 getLCM は、引数として
　M：$${2}$$以上の整数　整数（int）型
　N：$${2}$$以上の整数　整数（int）型
　prime_numbers：素数が格納された整数型可変配列　ArrayList<Integer>
を与え、返り値として
　整数$${M}$$と$${N}$$の最大公約数や最小公倍数　整数（int）型
となるように作成してください。

ヒント

関数の作成については、記事『高校数学をプログラミングで解く（準備編）「3-2 関数の作成」』の返り値を返す関数の節で説明していますので、そちらをご覧ください。
また、可変配列については、記事『高校数学をプログラミングで解く（準備編）「2-4 配列」』の可変配列（ArrayList）の節をご覧ください。

以下のソースコード1は、関数 getGCD と getLCM とを利用して、$${M=12}$$と$${N=30}$$を$${M=12}$$と$${N=60}$$の最大公約数や最小公倍数を求めて、結果の素数をコンソールに出力するプログラムになります。（課題（38日目、2024年7月24日）で作成した整数$${N}$$以下の素数を求める関数 getPrimeFactors と課題（40日目、2024年7月26日）で作成した整数$${N}$$を素因数分解する関数 primefactorization を再利用しています。）ただし、関数 getGCD や getLCM はまだ作成していません。

// 整数MとNの最大公約数や最小公倍数を求める関数
void setup(){
  // 整数M,N（ただし、2以上の整数）
  int M, N;
  M = 12;
  N = 30;
  
  // MとNのうち、大きい方を整数N_gtとし、N_gt以下の素数を求める
  int N_gt;
  if( M > N ){
    N_gt = M;
  } else {
    N_gt = N;
  }  
  // N_gt以下の素数を求める
  ArrayList<Integer> prime_numbers = getPrimeFactors(N_gt);
  
  // 最大公約数を求める
  int GCD = getGCD(M,N,prime_numbers);
  println("最大公約数:",GCD);
  int LCM = getLCM(M,N,prime_numbers);
  println("最小公倍数:",LCM);
}

// 整数N以下の素数を求める関数
ArrayList<Integer> getPrimeFactors(
  int N // 2以上の整数
){
  // int型の可変配列を準備する
  ArrayList<Integer> prime_numbers = new ArrayList<Integer>();
  // 最初の素数2を可変配列に追加
  prime_numbers.add(2);
 
  boolean pn_flag; // 素数かどうかのフラグ
  // 3以上N以下の整数について素数であるかを確認する
  for(int n=3; n<=N; n++){
    pn_flag = true;
    for(int m=2; m<n; m++){
      if( n%m == 0 ){ // mで割り切れたらnは素数でない
        pn_flag = false;
      }
    }
    if(pn_flag){
      prime_numbers.add(n); // iが素数と判定された場合、可変配列に追加
    }
  }
  
  return prime_numbers;
}

// 素因数分解を行う関数
ArrayList<Integer> primefactorization(
  int N, // 2以上の整数
  ArrayList<Integer> prime_numbers // N以下の素数
){
  // 素因数分解したときの各冪に対する指数
  ArrayList<Integer> exponents = new ArrayList<Integer>();
  
  // 整数Nを素因数分解する
  boolean divisible_flag; // 割り切れたかどうかを判定するフラグ
  int quotient = N; // 素数で割ったときの商
  int pn; // 素数を代入する変数
  int exponent_count;
  for(int i=0; i<prime_numbers.size(); i++){
    pn = prime_numbers.get(i); // i番目の素数を取り出す
    divisible_flag = true;
    exponent_count = 0;
    while(divisible_flag){
      if( quotient % pn == 0 ){ // 商が素数pnで割り切れた場合
        exponent_count++; // pnに対する指数の値を1増やす
        quotient = quotient / pn; // 商を更新する
      } else { // 素数pnがNの素因数ではない、またはpnがNの素因数としてすべて算出された場合
        divisible_flag = false; 
      }
    }
    exponents.add(exponent_count);
  } 
  
  return exponents;
}

// 整数MとNの最大公約数を求める関数
int getGCD(
  int M,
  int N,
  ArrayList<Integer> prime_numbers
){

  // MとNの最大公約数を求める処理を記述する
  
  return (int)GCD;
}

// 整数MとNの最小公倍数を求める関数
int getLCM(
  int M,
  int N,
  ArrayList<Integer> prime_numbers
){

  // MとNの最小公倍数を求める処理を記述する

  return (int)LCM;
}

ソースコード1　関数を利用して最大公約数や最小公倍数を求めて、結果をコンソールに出力するプログラム（未完成）

ソースコード1の getGCD 関数内の

  // MとNの最大公約数を求める処理を記述する

の部分や getLCM 関数内の

  // MとNの最小公倍数を求める処理を記述する

の部分に、それぞれ整数$${M}$$と$${N}$$の最大公約数を求める処理や整数$${M}$$と$${N}$$の最小公倍数を求める処理を実装して、getGCD 関数と getLCM 関数を完成させてください。

なお、一昨日、昨日作成した$${M}$$と$${N}$$の最大公約数や最小公倍数を求めるプログラムの中身を一旦 getGCD 関数や getLCM 関数内にそれぞれコピーしてから始めるとよいでしょう。

それでは、よろしくお願いします。

MK's papa