C++で1からNまでの範囲のうちXで割り切れ、かつYでは割り切れない数をカウントする方法

はじめに

整数 N が与えられたとき、1 から N までの範囲に含まれる数のうち、「X で割り切れるが Y では割り切れない」数の個数を求めるのが本記事の目的です。

具体例を見てみましょう。

例1

入力:

N=20 X=5 Y=20

出力:

1からNまでのうちXで割り切れYでは割り切れない数: 2

解説:

5と15のみが5で割り切れ、10では割り切れません。

例2

入力:

N=20 X=4 Y=7

出力:

1からNまでのうちXで割り切れYでは割り切れない数: 5

解説:

4、8、12、16、20 の5つの数は4で割り切れますが、7では割り切れません。

プログラムのアプローチ

• 整数 N を入力として受け取ります。
• 関数 divisibleXY(int x, int y, int n) は、1 から N までの範囲で X で割り切れ、かつ Y では割り切れない数の個数を返します。
• カウント用の変数 count を初期値 0 で宣言します。
• for ループを使って i = 1 から i = n まで順に走査します。
• 各数値 i に対して「i % x == 0 かつ i % y != 0」という条件を判定し、真であれば count をインクリメントします。
• 最後に count を結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int divisibleXY(int x, int y, int n){
    int count = 0;
    for (int i = 1; i <= n; i++) {
       if(i%x==0 && i%y!=0 )
          { count++; }
   }
   return count;
}
int main(){
   int N = 100;
   int X=6, Y=8;
   cout <<"1からNまでのうちXで割り切れYでは割り切れない数: "<< divisibleXY(X,Y,N);
   return 0;
}

出力

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

1からNまでのうちXで割り切れYでは割り切れない数: 12

補足：より効率的な計算方法

上記の方法は O(N) の時間計算量を持ちますが、数学的な性質を使うと O(1) で求めることも可能です。1 から N までの間で X の倍数の個数は「N / X」（小数点以下切り捨て）、XY の公倍数（最小公倍数 LCM）の倍数の個数は「N / LCM(X, Y)」となります。したがって、答えは次の式で計算できます。

count = (N / X) - (N / lcm(X, Y));

この方法を使えば、N が非常に大きい場合でも高速に答えを求めることができます。