高校数学をプログラミングで解く（数学A編）「3-4 自然数の積と素因数の個数」

マガジンリスト　＞　数学A編 3.整数の性質　＞　3-4 自然数の積と素因数の個数

はじめに

今回は、数学Aで学ぶ「自然数の積と素因数の個数」について、関連する2つの問題を解くプログラムを作成します。

互いに素となる自然数の個数を数える問題

問題
100 以下の自然数で、15 と互いに素である自然数の数を求めよ。

アルゴリズム設計（解法）

この個数は

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

で計算できますが、今回は 100 以下の自然数を一つ一つ、15 と互いに素であるかどうか調べていくことでその個数を数えていきます。2つの自然数が互いに素であるかどうかは2つの自然数の最大公約数が 1 になっているかどうかで判定します。2つの自然数の最大公約数を求めるプログラムはすでに記事『高校数学をプログラミングで解く（数学A編）「3-2 最大公約数と最小公倍数」』で作成していますので、このプログラムを関数化して利用します。

プログラム

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 GCD; // 最大公約数
  int count = 0; // N_compと互いに素となる自然数を数える
  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は互いに素となる
//      println(n);
        count++; // countの値を1増やす 
    }
  }
  println(count);
}

ソースコード1　互いに素となる自然数の個数を数えるプログラム

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

  return prime_numbers;
}

ソースコード2　自然数$${N}$$以下の素数を求める関数

// 素因数分解を行う関数
ArrayList<Integer> primefactorization(
  int N, // 素因数分解対象の自然数
  ArrayList<Integer> prime_numbers // 素数
){
  // 素因数分解したときの各冪に対する指数
  ArrayList<Integer> exponents = new ArrayList<Integer>();
  
  int quotient = N; // 素数で割ったときの商
  int pn;
  boolean divisible_flag; // 割り切れたかどうかを判定するフラグ
  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で割り切れた場合
        quotient = quotient / pn; // 商を更新する
        exponent_count++; // pnに対する指数の値を1増やす 
      } else { // 素数pnがNの素因数ではない、またはpnがNの素因数としてすべて算出された場合
        divisible_flag = false; 
      }
    }
    exponents.add(exponent_count);
  }

  return exponents;
}

ソースコード3　整数$${N}$$を素因数分解する関数

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

ソースコード4　整数$${M}$$と$${N}$$の最大公約数を求める関数

ソースコード1、ソースコード2、ソースコード3及びソースコード4を、Processingの開発環境ウィンドウを開いて（スケッチ名を「countNaturalNumber」としています）、テキストエディタ部分に書いて実行すると、図1のように、コンソールに 100 以下の自然数で、15 と互いに素である自然数の数「53」を出力します。

図1　スケッチ「countNaturalNumber」の実行結果

以下、整数$${M}$$と$${N}$$の最大公約数を求める関数（ソースコード4）に関してポイントを解説しておきます。

プログラムの解説（整数MとNの最大公約数の型について）

今回のプログラムでは、整数$${M}$$と$${N}$$の最大公約数を最初 float 型で計算して、最後に関数の戻り値として出力する際に、「(int)GCD」とすることで int 型に変えています（このように型を変換することを「キャスト」と呼びます）。
なぜわざわざこのような処理をしたかというと、pow 関数を利用してプログラムをシンプルにしたかったからです。例えば$${3^{10}}$$を計算する際、forループを用いて 3 を 10 回掛けるということができますが、多少プログラムが煩雑になります。そこで pow 関数を利用すると、$${3^{10}}$$は

pow(3, 10);

で計算することができ、プログラムをシンプルに書くことができます。ただし、pow 関数は引数と返り値ともに、float型になります。そのため、ソースコード4において最大公約数の値を計算する際は float 型で行い、最後に返り値として出力する際に int 型にキャストしたわけです。

自然数の中の特定の素因数の個数を数える問題

問題
1 から 150 までの 150 個の自然数の積$${N=1 \cdot 2 \cdot \cdots \cdot 150}$$について$${N}$$を素因数分解したときの素因数 3 の個数を求めよ。

アルゴリズム設計（解法）

素因数 3 の個数は、150 以下の自然数のうち、

$$
3\mathrm{の倍数の個数}(50) \\ +9\mathrm{の倍数の個数}(16) \\ +27\mathrm{の倍数の個数}(5) \\ +81\mathrm{の倍数の個数}(1) \\ = 72
$$

で計算できますが、今回は 1 から 150 までの一つ一つを素因数分解してそれぞれの素因数 3 の個数を取り出してきてそれらの総和を求めることで算出します。

プログラム

1から150までの積の中の素因数3の個数を求めてコンソールに出力するプログラムを作成します。

// 1から150までの150個の自然数N=1・2・…・150について
// Nを素因数分解したとき、素因数3の個数
void setup(){

  int N_max = 150; // Nの積の最大値
  int selected_prime_number = 3; // 選ばれた素因数 
 
  // N_max以下の素数を求める
  ArrayList<Integer> prime_numbers = getPrimeFactors(N_max);
  
  // 数値3が入っている位置
  int selected_index = prime_numbers.indexOf(selected_prime_number);
  
  // 1から150までをそれぞれ素因数分解して、素因数3の個数を数えていく
  int count = 0;
  ArrayList<Integer> exponents;
  for(int n=1; n<=N_max; n++){
    exponents = primefactorization(n, prime_numbers);
    count += exponents.get(selected_index);
  }
  
  println(count);
}

ソースコード5　1 から 150 までの積の中の素因数 3 の個数を求めるプログラム

なお、 自然数$${N}$$以下の素数を求める関数「getPrimeFactors」（ソースコード 2）や整数$${N}$$を素因数分解する関数「primefactorization」（ソースコード 3）を利用しています。

ソースコード5、ソースコード2及びソースコード3を、Processingの開発環境ウィンドウを開いて（スケッチ名を「countPrimeNumber」としています）、テキストエディタ部分に書いて実行すると、図2のように、コンソールに素因数 3 の個数「72」を出力します。

図2　スケッチ「countPrimeNumber」の実行結果

プログラムの解説（素因数3の個数を取り出す方法）

ソースコード5において、

  // N_max以下の素数を求める
  ArrayList<Integer> prime_numbers = getPrimeFactors(N_max);

の部分では、150 以下の素数を求めて、可変配列 prime_numbers に代入しています。この可変配列 prime_numbers には、最初の要素（0番目）に「2」、次の要素（1番目）に「3」、その次の要素（2番目）に「5」、というように素数が小さい順に入っています。
一方、

exponents = primefactorization(n, prime_numbers);

の部分では、整数$${n}$$を素因数分解し、素因数の各冪に対する指数を可変配列 exponents に代入しています。たとえば、$${n=12}$$とすると、

$$
12=2^2 \cdot 3^1 \cdot 5^0 \cdot \cdots
$$

と素因数分解できるので、可変配列 exponents には最初の要素（0番目）に2の冪に対する指数「2」、次の要素（1番目）に3の冪に対する指数「1」、その次の要素（2番目）に5の冪に対する指数「0」、というように底（素数）が小さい順に指数の値が入っています。
ポイントは、これらの2つの可変配列 prime_numbers と exponents は対応する順番が一致しているということです。例えば、今回注目する素因数「3」は prime_numbers の1番目の要素に入っており、素因数分解したときの「3」の冪に対する指数は exponents の1番目の要素に入っています。
これらのことを考慮して、今回素因数 3 の個数を次の手順で取り出しています。
①まず、素因数「3」が可変配列 prime_numbers の何番目に入っているかを取得します。これには、可変配列に対して利用できる関数 indexOf を利用します。

  // 数値3が入っている位置
  int selected_index = prime_numbers.indexOf(selected_prime_number);

素因数「3」は可変配列 prime_numbers の1番目に入っているので、この関数 indexOf の引数に selected_prime_number（=3）を指定すると「1」を取り出して、変数 selected_index に代入しています。
②次に、素因数分解したときの「3」の冪に対する指数を可変配列 exponents から取り出します。可変配列 exponents の要素を取り出すには、可変配列に対して利用できる関数 get を利用します。

exponents.get(selected_index);

素因数分解したときの「3」の冪に対する指数は可変配列 exponents の selected_index（=1）番目に入っているので、この関数 get の引数にselected_index（=1）を指定すると「3」の冪に対する指数を取り出すことができます。

まとめ

今回は、数学Aで学ぶ「自然数の積と素因数の個数」について、関連する2つの問題を解くプログラムを作成してみました。
2つの問題共、「アルゴリズム設計（解法）」の節で説明したように、うまく個数を数えればプログラムで解かずとも比較的簡単に答えを出すことはできます。ただ、今回のように単純に数を数える方法で解いておくこともよい経験になります。実際、今回の問題について、単純な方法（一つ一つ互いに素であるか判別したり、一つ一つ素因数分解したりする方法）で行っていくことは手計算では非常に大変な作業になりますが、コンピュータはこのような単純な反復作業を得意としていてすぐに解いてくれます。
このように、敢えて遠回りなことをコンピュータにさせることで、自分で計算した方がよいこと、コンピュータにやらせた方がよいことがだんだん区別できるようになってきます。

読んだ感想などをお寄せください

本記事を読んだ感想や質問などを以下のお問い合せフォームからお寄せください。感想、質問をいただいた方には本記事の演習問題の解答をプレゼントします。（お問合せフォームの本文に、本記事のタイトルを入れてください。）

お問い合わせ | note（ノート）

参考文献

改訂版 教科書傍用 スタンダード 数学A（数研出版、ISBN9784410209277）

演習問題

1 から 125 までの 125 個の自然数の積$${N=1 \cdot 2 \cdot 3 \cdot \cdots \cdot 125}$$を計算すると、末尾には 0 が連続して何個並ぶかを求めるプログラムを作成してください。

演習問題の解答例