高校数学１０分プログラミング（55日目、2024年8月16日）解説

本日の課題、おつかれさまでした。

素数に関連する問題を解くプログラムを作成することができたでしょうか。

解答例

$${60/n}$$の値が素数となる$${n}$$の値をすべて求めて、その結果をコンソールに出力するプログラムの例は以下のようになります。

// 60/nが素数になる整数nをすべて求める
void setup(){
  // 整数N（ただし、Nは2以上）
  int N;
  N = 60;

  // 整数N以下の素数を求める
  ArrayList<Integer> prime_numbers = getPrimeFactors(N);
 
  // 素因数分解したときの各冪に対する指数を求める
  ArrayList<Integer> exponents =  primefactorization(N, prime_numbers); 
  
  // 60/nが素数になるnの結果をコンソールに出力する
  int pn, exponent;
  for(int i=0; i<prime_numbers.size(); i++){
    exponent = exponents.get(i);
    if( exponent != 0){
      pn = prime_numbers.get(i);
      println(N/pn);
    }
  }
}

// 整数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;
}

ソースコード2　$${60/n}$$の値が素数となる$${n}$$の値をすべて求めて、その結果をコンソールに出力するプログラム

Processing の開発環境ウィンドウを立ち上げて、そのテキストエディタ部分にソースコード2を書き写し、実行ボタン（左上の ▶ ボタン）を押すと、コンソールに

30
20
12

と出力されます（図1）。

図1　コンソールに「30 20 12」と出力される

プログラムの解説

整数$${N}$$を素因数分解する関数 primefactorization の返り値は、
　素因数分解したときの各冪に対する指数　ArrayList<Integer>
となっています。例えば$${N＝60}$$は

$$
N = 2^2 \cdot 3^1 \cdot 5^1 \cdot 7^0 \cdot \cdots
$$

と素因数分解されますので、返り値は、

$$
2, 1, 1, 0, \cdots
$$

をこの順番で格納した整数型可変配列となります。
上記の$${60}$$の素因数分解の結果から、$${60/n}$$の値は$${2,3,5}$$の3つの素数になりえます。この3つの素数は、関数 primefactorization の返り値が$${0}$$でない素数を選び出すことで求めることができます。
あとは、$${60/n}$$の値が素数となる$${n}$$の値は$${60}$$を選び出された素数$${2,3,5}$$で割ったときの商となるので、それぞれ$${30, 20, 12}$$の3つとなります。
以上の処理がソースコード2の

  // 60/nが素数になるnの結果をコンソールに出力する
  int pn, exponent;
  for(int i=0; i<prime_numbers.size(); i++){
    exponent = exponents.get(i);
    if( exponent != 0){
      pn = prime_numbers.get(i);
      println(N/pn);
    }
  }

の部分となっています。

今週は以上です。また、今日で数学Aに関連するプログラミング課題は一旦終了となります。
来週からは、数学Iに関連するプログラミング課題を出題していきます。

来週からも引き続きよろしくお願いします。

※今回の課題とその解答例について質問や疑問がある方は、本記事の下部にあるコメント欄からお願いします。

MK’s papa