XまたはYで割り切れる最初のN個の自然数の合計を求める方法

nまでの自然数のうち、XまたはYで割り切れる数をすべて合計するとは、XまたはYで割り切れる数を選び出し、合計を格納する変数に加算していくことを指します。

XまたはYで割り切れる最初のN個の自然数の合計を求めるには、主に次の2つの方法があります。

• ループと条件文を使用する方法
• 数式を使用する方法

方法1:ループと条件文を使用する

この方法では、n個までカウントするループを使用し、XまたはYで割り切れる数を選択して、各反復ごとに合計変数へ加算していきます。

サンプルコード

#include <stdio.h>
int main(void) {
    int n = 54;
    int x = 2;
    int y = 5;
    int sum = 0;
    for(int i = 0; i<= n; i++) {
        if(i%x == 0 || i%y == 0)
            sum = sum + i;
    }
    printf("sum of %d natural numbers divisible by %d and %d is %d", n, x, y, sum);
    return 0;
}

出力

sum of 54 natural numbers divisible by 2 and 5 is 881

方法2:数式を使用する

この方法では、ある数で割り切れる最初のn個の数の合計を求めるための数式を使用します。

数xで割り切れるn個の自然数の合計は、次の式で求められます。

S_n/x = ((n/x)/2) × (2 × x + (n/x − 1) × x)

同様に、数yで割り切れるn個の自然数の合計は次のようになります。

S_n/y = ((n/y)/2) × (2 × y + (n/y − 1) × y)

さらに、x×yで割り切れるn個の自然数の合計は、次の式で求められます。

S_n/(x*y) = ((n/(x*y))/2) × (2 × (x*y) + (n/(x*y) − 1) × (x*y))

ここで、xの合計とyの合計を加算した後、二重に加算されてしまったx×yの合計を差し引きます。これは「包除原理」と呼ばれる考え方に基づいています。

サンプルコード

#include <stdio.h>
int main() {
    int n = 54;
    int x = 2, y = 5;
    int Sx, Sy, Sxy, sum;
    Sx = ((n / x)) * (2 * x + (n / x - 1) * x) / 2;
    Sy = ((n / y)) * (2 * y + (n / y - 1) * y) / 2;
    Sxy = ((n / (x * y))) * (2 * (x * y) + (n / (x * y) - 1) * (x * y)) / 2;
    sum = Sx + Sy - Sxy;
    printf("sum of %d natural numbers divisible by %d and %d is %d", n, x, y, sum);
    return 0;
}

出力

sum of 54 natural numbers divisible by 2 and 5 is 881

どちらの方法を選ぶべきか

2番目の数式を使う方法は、ループを使用しないため時間計算量の面で優れており、特に大きな入力に対して効率的です。一方、入力サイズが小さい場合は、1番目のループによる方法でも十分に実用的です。大規模なデータを扱う場合には、数式を用いた方法が最適な選択となります。