C++で素因数が2と3しかない範囲から数を数えます

数値の範囲を定義するために、STARTとENDの2つの数値が提供されています。目標は、素因数が2と3のみで、[START、END]の範囲にある数値を見つけることです。

これを行うには、STARTからENDまで数値をトラバースし、数値ごとに、数値が2と3でのみ割り切れるかどうかを確認します。割り切れる場合は、除算して減らします。そうでない場合は、ループを解除します。結局、数が1に減ると、その要因は2と3だけになります。

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

入力

START=20 END=25

出力

Numbers with only 2 and 3 as prime factors: 1

説明

Prime factors of each number:
20 = 2*2*5
21 = 3*7
22 = 2*11
23 = 1*23
24 = 2*2*2*3
25 = 5*5
Only 24 has 2 and 3 as prime factors.

入力

START=1000 END=1500

出力

Numbers with only 2 and 3 as prime factors: 4

説明

1024 1152 1296 1458 are the numbers with only 2 and 3 as prime factors

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

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

• 関数twothreeFactors（int start、int end）は範囲変数を受け取り、2と3を素因数としてのみ数を返します。

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

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

• 次に、数値num =iごとに、whileループを使用してnum％2 ==0かどうかをチェックし、それを除算します。

• num％3 ==0の場合、それを除算します。そうでない場合は、両方でwhileループを中断します

• whileループの数が1の場合は、カウントを増やします。

• すべてのループの終わりに、カウントは素因数として2と4だけを持つ総数になります。

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

例

#include <bits/stdc++.h>
using namespace std;
int twothreeFactors(int start, int end){
   // Start with 2 so that 1 doesn't get counted
   if (start == 1)
      { start++; }
   int count = 0;
   for (int i = start; i <= end; i++) {
      int num = i;
      while(num>1){
         // if divisible by 2, divide it by 2
         if(num % 2 == 0)
            { num /= 2; }
         // if divisible by 3, divide it by 3
         else if (num % 3 == 0)
            { num /= 3; }
         else //if divisible by neither 2 nor 3 break
            { break; }
      }
      // means only 2 and 3 are factors of num
      if (num == 1)
         { count++; }
   }
   return count;
}
int main(){
   int START = 10, END = 20;
   cout <<"Numbers with only 2 and 3 as prime factors:"<< twothreeFactors(START,END);
   return 0;
}

出力

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

Numbers with only 2 and 3 as prime factors:3