C++のすべての配列要素で割り切れる範囲の数値をカウントします

数値の範囲を定義するために、STARTとENDの2つの数値が提供されています。また、正の数の配列Arr[]。目標は、Arr []のすべての要素で割り切れる、[START、END]の範囲内にあるすべての数値を見つけることです。

方法1（ナイーブアプローチ）

これを行うには、STARTからENDまで数値をトラバースし、数値ごとに、その数値が配列のすべての要素で割り切れるかどうかを確認します。はいの場合、カウントをインクリメントします。

方法2（配列要素のLCMによる除算性を確認する）

すべての配列要素のLCMを見つけて、そのLCMで完全に割り切れる[START、END]の範囲内のすべての数値をチェックしてカウントします。

例を挙げて理解しましょう。

入力

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

出力

Numbers that are divisible by all array elements: 2

説明

Numbers 8 and 16 are in the range that are divisible by all array elements.

入力

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

出力

Numbers that are divisible by all array elements: 0

説明

No number between 100 to 200 divisible by any array element.

方法1（ナイーブアプローチ）

以下のプログラムで使用されているアプローチは次のとおりです

• 整数のSTARTとENDを範囲変数として使用します。

• 関数divisiblebyArr（int start、int end、int arr []、int len）は、範囲変数と配列を受け取り、すべての配列要素で割り切れる数の数を返します。

• このような数値の場合、初期変数カウントを0とします。

• 変数フラグを0とします

• forループを使用して数値の範囲をトラバースします。 i=開始から終了

• ここで、数値num =iごとに、whileループを使用して、数値がすべての配列要素で割り切れるかどうかを確認します。

• すべての要素がnumを完全に分割する場合は、flag=1を設定します。

• フラグ=1の場合は増分カウント

• すべてのループの終わりに、カウントは配列のすべての要素で割り切れる総数になります。

• 結果としてカウントを返します。

例

#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 <<"Numbers that are divisible by all array elements: "<< divisiblebyArr(START,END,Arr,len);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Numbers that are divisible by all array elements: 2

方法2（LCMアプローチ）

以下のプログラムで使用されているアプローチは次のとおりです

• 整数のSTARTとENDを範囲変数として使用します。

• 関数getLCM（int a、int b）は、2つの数値を受け取り、whileループを使用して両方で割り切れる最初の数値を見つけることにより、それらのLCMを返します。

• 関数getLCMArray（int arr []、int n）は、配列とその長さを入力として受け取り、配列のすべての要素のLCMを返します。

• 最初のLCMをgetLCM（arr [0]、arr [1]）として計算します。その後、getLCM（lcm、arr [i]）を呼び出して、前のlcmとarr [i]のlcmを連続して見つけます。ここで、i=2からi

• 関数divisiblebyArr（int start、int end、int arr []、int len）は、範囲変数と配列を受け取り、すべての配列要素で割り切れる数の数を返します。

• このような数値の場合、初期変数カウントを0とします。

• 変数lcmをgetLCMArray（int arr []、int len）として取得します。

• forループを使用して数値の範囲をトラバースします。 i=開始から終了

• ここで、各数値iについて、それが分割可能なlcmであるかどうかを確認します。 trueの場合、カウントをインクリメントします。

• すべてのループの終わりに、カウントは配列のすべての要素で割り切れる総数になります。

• 結果としてカウントを返します。

例

#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 <<"Numbers that are divisible by all array elements: "<< divisiblebyArr(START,END,Arr,len);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Numbers that are divisible by all array elements: 2