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

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

互いに素となる自然数の個数を数えるプログラムを作成することができたでしょうか。

解答例

100以下の自然数で、15と互いに素である自然数の数を求めて、結果をコンソールに出力するプログラムの例は以下のようになります。

// 100以下の自然数で、15と互いに素である自然数の数
void setup(){

  int N_max, N_comp;
  N_max = 100;
  N_comp = 15;
 
  // N_max以下の素数を求める
  ArrayList<Integer> prime_numbers = getPrimeFactors(N_max);
  
  int count = 0; // N_compと互いに素となる自然数を数える
  int GCD; // 最大公約数
  for(int n=1; n<=N_max; n++){
    GCD = getGCD(n, N_comp, prime_numbers); // nとN_compの最大公約数
    if(GCD == 1){ // 最大公約数が1のとき、nとN_compは互いに素となる
        count++; // countの値を1増やす 
    }
  }
  println(count);
}

// 整数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をそれぞれ素因数分解する
  ArrayList<Integer> exponents_M = primefactorization(M, prime_numbers);
  ArrayList<Integer> exponents_N = primefactorization(N, prime_numbers);

  // MとNの最大公約数を求める
  float GCD = 1.0; // 最大公約数
  int exponents_GCD; // 最大公約数を素因数分解した時のi番目の冪の指数
  for(int i=0; i<prime_numbers.size(); i++){
    if( exponents_M.get(i) < exponents_N.get(i)){
      exponents_GCD = exponents_M.get(i);
    } else {
      exponents_GCD = exponents_N.get(i);
    }
    GCD = GCD * pow(prime_numbers.get(i), exponents_GCD);
  }
  
  return (int)GCD;
}

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

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

53

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

図1　コンソールに 53 と出力される

なお、今回の課題は、解析的に

$$
100-\left(3\mathrm{の倍数の個数}(33)+5\mathrm{の倍数の個数}(20)-15\mathrm{の倍数の個数}(6) \right) \\ = 53
$$

と計算することができますので、プログラム（ソースコード2）が正しい値を出力していることがわかります。

やってほしいこと

課題で説明した、
『100以下の自然数を一つ一つ、15と互いに素であるかどうか調べていくことでその個数を数えてください。2つの自然数が互いに素であるかどうかは2つの自然数の最大公約数が1になっているかどうかで判定します。』
の部分とプログラム（ソースコード2）の

  int GCD; // 最大公約数
  for(int n=1; n<=N_max; n++){
    GCD = getGCD(n, N_comp, prime_numbers); // nとN_compの最大公約数
    if(GCD == 1){ // 最大公約数が1のとき、nとN_compは互いに素となる
        count++; // countの値を1増やす 
    }
  }

の部分が対応していますので、今一度これらの対応関係を確認しておいてください。

本日は以上です。
明日は、自然数の中の特定の素因数の個数を数えるプログラムについて考えていきたいと思います。

明日もよろしくお願いします。

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

MK’s papa