C++でN以下の2または3または5の倍数を検索します

---

この問題では、数値Nが与えられます。私たちのタスクは、N以下の2または3または5の倍数を見つけることです。

問題の説明 − 2、3、または5で割り切れる1からNまでのすべての要素をカウントします。

問題を理解するために例を見てみましょう

入力

N = 7

出力

5

説明

All the elements from 1 to 7 are : 1, 2, 3, 4, 5, 6, 7.
Elements divisible by 2/3/5 are 2, 3, 4, 5, 6

ソリューションアプローチ

この問題を解決する簡単な方法は、1からNまでのすべての数値をトラバースし、2、3、または5で割ったすべての数値を数えることです。

アルゴリズム

初期化 −カウント=0

ステップ1 − i=1からNへのループ。

ステップ1.1 ：if（i％2 ==0 || i％3 ==0 || i％5 ==0）、count++。

ステップ2 −リターンカウント。

別のアプローチ

問題を解決するためのより効果的なアプローチは、集合論を使用することです。

2で割り切れる数の数はn（2）

です。

3で割り切れる数の数はn（3）

です。

5で割り切れる数の数はn（5）

です。

2と3で割り切れる数の数はn（2 n 3）

です。

2と5で割り切れる数の数はn（2 n 5）

です。

3と5で割り切れる数の数はn（3 n 5）

です。

2と3と5で割り切れる数の数はn（2 n 3 n 5）

です。

2または3または5で割り切れる数の数はn（2 U 3 U 5）

です。

集合論に基づく

n（2∪3∪5）=n（2）+ n（3）+ n（5）-n（2∩3）-n（2∩5）-n（3∩5）+ n（2∩3 ∩5）

解は、数値のビットマスクを計算することによって見つけられます。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;
int countMultiples(int n) {
   int values[] = { 2, 3, 5 };
   int countMultiples = 0, bitMask = pow(2, 3);
   for (int i = 1; i < bitMask; i++) {
      int prod = 1;
      for (int j = 0; j < 3; j++) {
         if (i & 1 << j)
            prod = prod * values[j];
      }
      if (__builtin_popcount(i) % 2 == 1)
         countMultiples = countMultiples + n / prod;
      else
         countMultiples = countMultiples - n / prod;
   }
   return countMultiples;
}
int main() {
   int n = 13;
   cout<<"The number of multiples till "<<n<<" is "<<countMultiples(n)<<endl;
   return 0;
}

出力

The number of multiples till 13 is 9