Project Euler 1: 3 또는 5의 배수의 합을 O(1)로

Project Euler 시리즈의 첫 문제입니다. 반복문 한 줄로도 풀리는 문제지만, 같은 답을 반복 없이 상수 번의 연산으로 구하는 과정에 포함-배제와 등차수열의 합이라는 두 도구가 모두 들어 있습니다. 뒤의 문제에서도 계속 쓰이는 도구라 처음부터 꼼꼼히 유도해 둡니다.

문제

1000보다 작은 자연수 가운데 3의 배수이거나 5의 배수인 수를 모두 더한 값을 구합니다. 문제에는 작은 예가 함께 나옵니다. 10보다 작은 자연수 중 조건에 맞는 수는 3, 5, 6, 9이고, 합은 23입니다.

경계에 주의해야 합니다. “1000 미만”이므로 1000 자체는 들어가지 않습니다. 1000은 5의 배수이므로, 경계를 “1000 이하”로 잘못 읽으면 답이 정확히 1000만큼 커집니다.

필요한 배경 지식

나눗셈의 몫(바닥 나눗셈). ⌊a / b⌋는 a를 b로 나눈 몫, 즉 a/b 이하인 가장 큰 정수입니다. 양의 정수 n과 k에 대해 “n 미만인 k의 양의 배수”는 k, 2k, …, mk이고, 이때 m은 mk ≤ n − 1을 만족하는 가장 큰 정수이므로 m = ⌊(n − 1) / k⌋입니다. n 미만이라는 조건 때문에 n이 아니라 n − 1을 나눕니다. 예를 들어 n = 10, k = 5이면 ⌊9 / 5⌋ = 1이라 5 하나만 셉니다. ⌊10 / 5⌋ = 2를 쓰면 10까지 들어가 버립니다.

1부터 m까지의 합. 1 + 2 + … + m = m(m + 1) / 2입니다. 같은 합을 거꾸로 적어 위아래로 더하면 이유가 보입니다.

  1   +   2   + … +   m
  m   + (m−1) + … +   1
(m+1) + (m+1) + … + (m+1)   ← m개

두 줄의 합은 m(m + 1)이고, 원래 합은 그 절반입니다. m과 m + 1 중 하나는 짝수이므로 m(m + 1)은 언제나 짝수이고, 2로 나누어도 정수가 남습니다. 코드에서 정수 나눗셈을 써도 잘리는 부분이 없다는 뜻입니다.

등차수열의 합. k, 2k, …, mk는 공차가 k인 등차수열이고, 각 항에서 k를 묶어 내면 k(1 + 2 + … + m) = k · m(m + 1) / 2가 됩니다.

포함-배제 원리. 두 집합 A, B에 대해 |A ∪ B| = |A| + |B| − |A ∩ B|입니다. A와 B에 모두 속하는 원소는 |A|와 |B|에서 한 번씩, 모두 두 번 세어지므로 한 번을 빼야 합니다. 원소의 개수 대신 원소의 합에도 똑같이 성립합니다. 공통 원소의 값이 두 번 더해졌으니 한 번 빼면 됩니다.

최소공배수. 3의 배수이면서 5의 배수인 수는 3과 5의 공배수이고, 공배수는 최소공배수의 배수입니다. 3과 5는 서로소이므로 최소공배수는 3 × 5 = 15입니다.

가장 단순한 방법

1부터 999까지 하나씩 보면서 3이나 5로 나누어떨어지면 더합니다.

total = 0
for i in range(1, 1000):
    if i % 3 == 0 or i % 5 == 0:
        total += i

상한이 n이면 n − 1개의 수를 한 번씩 확인하므로 시간 복잡도는 O(n), 공간은 O(1)입니다. n = 1000이면 충분히 빠릅니다. 하지만 n이 10^12나 10^18처럼 커지면 반복 횟수도 그만큼 늘어나 현실적인 시간 안에 끝나지 않습니다.

흔한 실수도 하나 있습니다. “3의 배수의 합 + 5의 배수의 합”을 따로 반복해서 더하면 15, 30, 45처럼 둘 다에 속하는 수가 두 번 더해집니다. 위 코드는 or로 한 번만 더하므로 이 문제가 없지만, 아래의 공식 풀이에서는 이 중복을 직접 처리해야 합니다.

풀이 유도

1단계: 작은 예를 집합으로 나눕니다. n = 10일 때 10 미만의 3의 배수는 {3, 6, 9}, 5의 배수는 {5}입니다. 둘 다에 속하는 수, 즉 15의 배수는 10 미만에 없습니다.

2단계: 포함-배제를 적용합니다. “n 미만인 k의 양의 배수의 합”을 S(k, n)이라고 하면

답(n) = S(3, n) + S(5, n) − S(15, n)

입니다. n = 10이면 S(3, 10) = 3 + 6 + 9 = 18, S(5, 10) = 5, S(15, 10) = 0이고, 18 + 5 − 0 = 23으로 문제의 예와 같습니다.

3단계: S(k, n)을 닫힌 식으로 바꿉니다. 배경 지식의 두 식을 합치면

m = ⌊(n − 1) / k⌋
S(k, n) = k + 2k + … + mk = k · m(m + 1) / 2

입니다.

4단계: 작은 예로 공식을 검산합니다. n = 10에서

• k = 3: m = ⌊9 / 3⌋ = 3, S = 3 · 3 · 4 / 2 = 18
• k = 5: m = ⌊9 / 5⌋ = 1, S = 5 · 1 · 2 / 2 = 5
• k = 15: m = ⌊9 / 15⌋ = 0, S = 15 · 0 · 1 / 2 = 0

이고, 18 + 5 − 0 = 23입니다. 2단계에서 직접 나열해 더한 값과 같습니다. 이제 n = 1000에 같은 식을 쓰면 됩니다.

최종 알고리즘과 복잡도

1. S(k, n)을 계산하는 함수를 만듭니다. n이 0이면 0을 돌려주고, 아니면 m = ⌊(n − 1) / k⌋를 구한 뒤 k · (m(m + 1) / 2)를 돌려줍니다.
2. S(3, n) + S(5, n) − S(15, n)을 돌려줍니다.
3. 출력하기 전에 n = 10의 결과가 23인지 확인하고, 다르면 0이 아닌 종료 코드로 끝냅니다.

정확성. n 미만의 자연수 x 하나가 합에 몇 번 들어가는지 경우를 나눠 봅니다.

• x가 3의 배수지만 5의 배수가 아니면: S(3)에서 한 번 더해지고, S(5)와 S(15)에는 없습니다. 1번.
• x가 5의 배수지만 3의 배수가 아니면: S(5)에서만 한 번. 1번.
• x가 3과 5의 배수이면: 15의 배수이므로 S(3), S(5)에서 한 번씩 더해지고 S(15)에서 한 번 빠집니다. 1 + 1 − 1 = 1번.
• x가 둘 다의 배수가 아니면: 어느 항에도 없습니다. 0번.

조건에 맞는 수는 정확히 한 번, 맞지 않는 수는 한 번도 더해지지 않으므로 결과는 구하려는 합과 같습니다. 각 S(k, n)이 n 미만인 k의 배수를 빠짐없이, 중복 없이 더한다는 점은 배경 지식에서 보였습니다.

시간과 공간. n의 크기와 관계없이 나눗셈 세 번과 몇 번의 곱셈·덧셈만 하므로, 고정 폭 정수에서 시간 복잡도는 O(1), 공간 복잡도도 O(1)입니다. Python의 정수는 크기 제한이 없어서 아주 큰 n에서는 연산 하나의 비용이 자릿수에 따라 늘어나지만, 연산 횟수는 여전히 상수입니다.

정수 범위. n = 1000이면 가장 큰 중간값도 수십만 정도라 unsigned long long은 물론 일반적인 32비트 부호 없는 정수에도 여유 있게 들어갑니다. 그래도 일반적인 n을 염두에 두고 범위를 따져 둡니다.

• C++ 구현은 unsigned long long을 씁니다. C++ 표준은 이 타입이 최소 64비트임을 보장하고(C 표준의 ULLONG_MAX 최솟값을 따름), 부호 없는 정수의 연산은 2^N을 법으로 정의되어 있어서 부호 있는 정수와 달리 정의되지 않은 동작이 생기지 않습니다. 다만 범위를 넘으면 조용히 틀린 값이 나오므로, 넘지 않는 범위에서만 써야 합니다.
• S(k, n) 안에서는 m(m + 1) / 2를 먼저 계산한 뒤 k를 곱합니다. 2로 나누기 전의 곱은 k = 3일 때 가장 크며, n ≤ 2^32이면 m ≤ (2^32 − 1) / 3이고 m(m + 1)은 약 2.05 × 10^18로 2^64(약 1.84 × 10^19)보다 작습니다. 다만 전체에서 가장 큰 중간값은 뺄셈 전의 S(3) + S(5)입니다. 대략 n²/6 + n²/10, 즉 n²의 27% 정도라 n = 2^32에서 약 4.92 × 10^18이고, 이것도 2^64 미만입니다. 즉 이 C++ 코드는 n ≤ 2^32에서 안전합니다.
• 뺄셈 S(3) + S(5) − S(15)는 부호 없는 정수에서 음수가 될 걱정이 없습니다. 15의 배수는 모두 3의 배수이기도 하므로 S(15) ≤ S(3)이기 때문입니다.
• Python의 int는 정밀도에 제한이 없으므로 n이 아무리 커도 넘치지 않습니다. //는 바닥 나눗셈이고, 여기서는 피연산자가 모두 0 이상이라 C++의 /와 결과가 같습니다.

C++17 구현

#include <iostream>

// Sum of the positive multiples of k that are less than limit.
unsigned long long sum_of_multiples_below(unsigned long long k, unsigned long long limit) {
    if (limit == 0) {
        return 0;
    }
    const unsigned long long m = (limit - 1) / k;
    return k * (m * (m + 1) / 2);
}

// Sum of the natural numbers less than limit that are divisible by 3 or 5.
unsigned long long sum_of_multiples_of_3_or_5_below(unsigned long long limit) {
    return sum_of_multiples_below(3, limit) + sum_of_multiples_below(5, limit) -
           sum_of_multiples_below(15, limit);
}

int main() {
    if (sum_of_multiples_of_3_or_5_below(10) != 23) {
        return 1;
    }
    std::cout << sum_of_multiples_of_3_or_5_below(1000) << '\n';
    return 0;
}

limit == 0을 따로 처리하는 이유는 limit - 1이 부호 없는 정수에서 0 − 1이 되면 가장 큰 값으로 돌아가기 때문입니다. 이 문제에서 0을 넣을 일은 없지만, 이 검사 덕분에 limit == 0일 때 값이 돌아가지 않고 올바른 결과인 0을 돌려줍니다. 작은 예의 확인은 assert가 아니라 if로 했습니다. assert는 NDEBUG가 정의된 빌드에서 사라지기 때문입니다.

Python 3 구현

def sum_of_multiples_below(k: int, limit: int) -> int:
    """Sum of the positive multiples of k that are less than limit."""
    if limit <= 0:
        return 0
    m = (limit - 1) // k
    return k * (m * (m + 1) // 2)


def sum_of_multiples_of_3_or_5_below(limit: int) -> int:
    """Sum of the natural numbers less than limit that are divisible by 3 or 5."""
    return (
        sum_of_multiples_below(3, limit)
        + sum_of_multiples_below(5, limit)
        - sum_of_multiples_below(15, limit)
    )


def main() -> None:
    if sum_of_multiples_of_3_or_5_below(10) != 23:
        raise SystemExit(1)
    print(sum_of_multiples_of_3_or_5_below(1000))


if __name__ == "__main__":
    main()

C++와 같은 알고리즘, 같은 함수 구성입니다. 작은 예가 틀리면 raise SystemExit(1)로 종료 코드 1을 냅니다. assert는 python -O로 실행하면 제거되므로 쓰지 않았습니다.

정답과 검증

n = 1000에 공식을 적용하면 다음과 같습니다.

• k = 3: m = ⌊999 / 3⌋ = 333, S = 3 · (333 · 334 / 2) = 3 · 55611 = 166833
• k = 5: m = ⌊999 / 5⌋ = 199, S = 5 · (199 · 200 / 2) = 5 · 19900 = 99500
• k = 15: m = ⌊999 / 15⌋ = 66, S = 15 · (66 · 67 / 2) = 15 · 2211 = 33165

따라서 답은 166833 + 99500 − 33165 = 233168입니다.

검증은 세 겹으로 합니다.

1. 작은 예. 두 프로그램 모두 답을 출력하기 전에 n = 10의 결과가 문제에 주어진 23인지 확인하고, 다르면 0이 아닌 종료 코드로 끝납니다. 위의 “풀이 유도” 4단계에서 같은 값을 손으로도 확인했습니다.
2. 두 구현의 일치. 이 시리즈의 저장소에서는 검사 스크립트가 C++ 코드를 g++ -std=c++17 -O2 -Wall -Wextra -Werror로 컴파일해 실행하고(경고도 실패로 처리), Python 코드를 python3 -I -B로 실행합니다. 두 출력이 저장해 둔 answer.txt와 바이트 단위로 같아야 하고, 0이 아닌 종료 코드나 시간 초과(C++ 1초, Python 10초)는 실패입니다. 시리즈 규칙상 이 검사를 통과한 코드만 글에 싣습니다.
3. 손 계산. 바로 위에서 세 항을 직접 계산해 같은 값을 얻었습니다. 개수로도 맞춰 볼 수 있습니다. 999 이하의 3의 배수 333개, 5의 배수 199개, 15의 배수 66개이므로 조건에 맞는 수는 333 + 199 − 66 = 466개입니다. 위의 단순한 반복문으로 개수를 세어 비교해 보는 것도 좋은 연습입니다.

더 생각해 볼 것

• 경계 바꾸기. “1000 이하”라면 무엇이 바뀔까요? 함수에 limit = 1001을 넣으면 됩니다. 1000이 5의 배수라서 답이 1000만큼 커집니다.
• 약수 세 개로 늘리기. 3, 5, 7 중 하나 이상으로 나누어떨어지는 수의 합은 포함-배제를 세 집합으로 늘려 S(3) + S(5) + S(7) − S(15) − S(21) − S(35) + S(105)로 구합니다. 약수가 서로소가 아니면(예: 4와 6) 교집합은 곱이 아니라 최소공배수(12)의 배수라는 점에 주의하세요.
• 일반화. 약수가 d개이면 포함-배제 항은 2^d − 1개입니다. 약수가 많아지면 항 수가 급격히 늘어나므로, 어느 시점부터는 다른 방법이 나을 수 있습니다.
• 오버플로 실험. C++ 코드에서 n이 2^32를 크게 넘으면 어디서 먼저 넘치는지 계산해 보세요. Python으로 같은 n을 계산해 비교하면 차이를 확인할 수 있습니다.
• 이 시리즈의 다음 문제들. 1부터 m까지의 합 같은 닫힌 식은 1–100번 안의 다른 문제에서도 다시 나옵니다. 반복문으로 먼저 풀고, 닫힌 식으로 바꿀 수 있는지 따져 보는 습관을 들여 두면 도움이 됩니다.

출처

• Project Euler, Problem 1 — 원래 문제
• Project Euler, Copyright — 문제 본문의 라이선스(CC BY-NC-SA 4.0)
• C++17 최종 작업 초안 N4659 — §6.9.1 기본 타입(부호 없는 정수의 2^N 법 연산), §21.3.6 <climits>(C 표준의 범위를 따름), §22.3 assert(NDEBUG)
• Python 표준 라이브러리: Numeric Types — int의 무제한 정밀도와 //(바닥 나눗셈)
• Python 레퍼런스: The assert statement — 최적화 모드에서 assert가 제거됨