C++で配列の全要素により割り切れる範囲内の数値をカウントする方法

本記事では、2つの整数 START と END で定義される範囲、および正の整数からなる配列 Arr[] が与えられたとき、範囲 [START, END] 内に存在し、配列のすべての要素で割り切れる数値を求める方法を解説します。

入出力例

入力例1

START=1 END=20 Arr[]= { 2, 4, 8 }

出力

配列の全要素で割り切れる数値の個数: 2

解説： 範囲 [1, 20] の中で、配列の全要素（2・4・8）すべてで割り切れるのは 8 と 16 の2つです。

入力例2

START=100 END=200 Arr[]= { 230, 321, 490, 521 }

出力

配列の全要素で割り切れる数値の個数: 0

解説： 100〜200 の範囲には、配列の全要素で割り切れる数値は1つも存在しないため、0 を返します。

方法1：素朴なアプローチ（全数値を直接チェック）

この方法では、START から END までの数値を1つずつ順番に調べ、それぞれが配列のすべての要素で割り切れるかどうかを確認します。条件を満たす数値が見つかるたびにカウントを増やしていきます。

アルゴリズムの手順

• 整数 START と END を範囲を表す変数として受け取ります。
• 関数 divisiblebyArr(int start, int end, int arr[], int len) は、範囲と配列を受け取り、配列の全要素で割り切れる数値の個数を返します。
• 条件を満たす数値の個数を数えるため、カウンタ変数 count を 0 で初期化します。
• フラグ変数 flag を用意します。
• for ループで i = start から i = end まで、範囲内の数値を順に走査します。
• 各数値 num = i に対して、while ループで配列のすべての要素による割り切り判定を行います。
• すべての要素が num を余りなく割り切れた場合は flag を 1 に設定します。
• while ループを抜けた後、flag == 1 であれば count をインクリメントします。
• すべてのループが終了した時点で、count には配列の全要素で割り切れる数値の総数が格納されています。
• 最後に count を結果として返します。

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;
int divisiblebyArr(int start, int end, int arr[], int len){
   int count = 0;
   int flag=0;
   int index=0;
   for (int i = start; i <= end; i++){
      int num = i;
      index=0;
      while(index<len){
         if(num % arr[index++] == 0)
            { flag=1; }
         else{
            flag=0;
            break;
         }
      }
      if (flag == 1)
         { count++; }
      }
   return count;
}
int main(){
   int START = 5, END = 20;
   int Arr[] = {2,4,8 };
   int len=sizeof(Arr)/sizeof(Arr[0]);
   cout <<"配列の全要素で割り切れる数値の個数: "<< divisiblebyArr(START,END,Arr,len);
   return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

配列の全要素で割り切れる数値の個数: 2

方法2：最小公倍数（LCM）を使ったアプローチ

ある数が配列のすべての要素で割り切れるということは、その数が配列要素全体の最小公倍数（LCM）で割り切れることと同じです。そこで、まず配列全要素の LCM を求め、その LCM で割り切れる [START, END] 内の数値だけを数えます。この方法なら、各数値ごとに配列の全要素との剰余計算を繰り返す必要がありません。

アルゴリズムの手順

• 整数 START と END を範囲を表す変数として受け取ります。
• 関数 getLCM(int a, int b) は、2つの数のどちらでも割り切れる最初の数を while ループで探索し、その値を2数の LCM として返します。
• 関数 getLCMArray(int arr[], int n) は、配列とその長さを受け取り、配列の全要素の LCM を返します。
• まず getLCM(arr[0], arr[1]) で初期の LCM を計算します。その後、i = 2 から i < n まで、直前の LCM と arr[i] の LCM を getLCM(lcm, arr[i]) の呼び出しで順に求めていきます。
• 関数 divisiblebyArr(int start, int end, int arr[], int len) は、範囲と配列を受け取り、全要素で割り切れる数値の個数を返します。
• カウンタ変数 count を 0 で初期化します。
• 変数 lcm を getLCMArray(arr, len) の結果として取得します。
• for ループで i = start から i = end まで範囲内の数値を走査します。
• 各数値 i が lcm で割り切れる場合は、count をインクリメントします。
• すべてのループ終了後、count が答えとなります。
• count を結果として返します。

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;
int getLCM(int a, int b){
   int m;
   m = (a > b) ? a : b;
   while(true){
      if(m % a == 0 && m % b == 0)
         return m;
      m++;
   }
}
int getLCMArray(int arr[], int n){
   int lcm = getLCM(arr[0], arr[1]);
   for(int i = 2; i < n; i++){
      lcm = getLCM(lcm, arr[i]);
   }
   return lcm;
}
int divisiblebyArr(int start, int end, int arr[], int len){
   int count = 0;
   int flag=0;
   int lcm=getLCMArray(arr,len);
   for (int i = start; i <= end; i++){
      if(i%lcm==0)
         { count++; }
      }
   return count;
}
int main(){
   int START = 5, END = 20;
   int Arr[] = {2,4,8 };
   int len=sizeof(Arr)/sizeof(Arr[0]);
   cout <<"配列の全要素で割り切れる数値の個数: "<< divisiblebyArr(START,END,Arr,len);
   return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

配列の全要素で割り切れる数値の個数: 2

まとめ

方法1は実装がシンプルで分かりやすい一方、範囲内のすべての数値について配列の全要素との剰余計算を繰り返すため、範囲が広い場合や配列のサイズが大きい場合には非効率です。一方、方法2は LCM を一度求めてしまえば、各数値の判定が1回の剰余計算で済むため、はるかに高速です。ただし、配列の値によっては LCM が非常に大きくなる可能性があるため、実運用では long long 型の利用など、オーバーフローへの配慮も忘れないようにしましょう。