X 또는 Y로 나누어 떨어지는 처음 N개의 자연수의 합 구하기

X 또는 Y로 나누어 떨어지는 n 이하의 모든 자연수를 더한다는 것은, 조건에 맞는 숫자들을 골라내어 합계를 저장하는 변수에 차례로 누적하는 과정을 의미합니다.

X 또는 Y로 나누어 떨어지는 처음 N개의 자연수의 합을 구하는 방법은 크게 두 가지가 있습니다.

• 반복문과 조건문을 사용하는 방법
• 수학 공식을 사용하는 방법

방법 1 - 반복문과 조건문 사용하기

이 방법은 0부터 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 - 수학 공식 사용하기

이 방법은 등차수열의 합 공식을 응용하여, 특정 수로 나누어 떨어지는 자연수의 합을 반복문 없이 한 번에 계산합니다.

x로 나누어 떨어지는 n 이하 자연수의 합은 다음 공식으로 구할 수 있습니다.

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

같은 방식으로 y로 나누어 떨어지는 자연수의 합도 구합니다.

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

또한 x와 y의 공배수, 즉 x×y로 나누어 떨어지는 자연수의 합도 구합니다.

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

여기서 주의할 점은, x와 y의 공배수는 앞의 두 합에서 중복으로 더해진다는 것입니다. 따라서 포함-배제 원리(Inclusion-Exclusion Principle)에 따라 S_n/x와 S_n/y를 더한 뒤, 중복된 S_n/(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

두 방법의 비교

두 번째 방법은 반복문을 전혀 사용하지 않고 상수 시간(O(1))에 결과를 계산하므로 시간 복잡도 면에서 훨씬 유리합니다. 입력 크기가 작다면 첫 번째 방법도 충분히 실용적이지만, n이 커질수록 반복문 기반의 첫 번째 방법은 비효율적이므로 공식을 활용한 두 번째 방법을 사용하는 것이 좋습니다.