N 이하의 자연수 중 2 또는 5로 나누어 떨어지는 수들의 합은 다음과 같은 방식으로 구할 수 있습니다. 먼저 2로 나누어 떨어지는 수들의 합(Sum2)과 5로 나누어 떨어지는 수들의 합(Sum5)을 각각 구한 뒤 더하고, 여기서 10으로 나누어 떨어지는 수들의 합(Sum10)을 빼면 원하는 결과를 얻을 수 있습니다. 10의 배수는 2와 5의 공배수이므로 앞의 두 합에 중복으로 포함되기 때문입니다.
이 방법은 반복문 없이 등차수열의 합 공식만으로 한 번에 계산하기 때문에, n 값이 아무리 커져도 거의 일정한 성능을 유지하는 매우 효율적인 접근 방식입니다.
왜 반복문 대신 공식을 사용해야 할까?
반복문과 조건문을 사용해 2 또는 5로 나누어 떨어지는 수를 하나씩 더하는 방법도 떠올릴 수 있습니다. 하지만 이 방법은 시간 복잡도가 O(n)이므로 비효율적입니다. n이 커질수록 반복문이 n번 실행되고, 그만큼 프로그램의 부하와 실행 시간이 선형적으로 증가하게 됩니다.
반면 공식 기반 접근은 연산 횟수가 n과 무관하게 상수 번으로 끝나므로(O(1)), 매우 큰 n 값에서도 빠르게 동작합니다.
합을 구하는 공식
2로 나누어 떨어지는 자연수의 합:
Sum2 = ((n / 2) * (4 + (n / 2 - 1) * 2)) / 2
5로 나누어 떨어지는 자연수의 합:
Sum5 = ((n / 5) * (10 + (n / 5 - 1) * 5)) / 2
10으로 나누어 떨어지는 자연수의 합(중복 제거용):
Sum10 = ((n / 10) * (20 + (n / 10 - 1) * 10)) / 2
최종 결과는 위 세 값을 다음과 같이 조합하여 구합니다.
Sum = Sum2 + Sum5 - Sum10
C 언어 구현 예제
#include <stdio.h>
int main() {
int n = 25;
long int sum2, sum5, sum10;
sum2 = ((n / 2) * (4 + (n / 2 - 1) * 2)) / 2;
sum5 = ((n / 5) * (10 + (n / 5 - 1) * 5)) / 2;
sum10 = ((n / 10) * (20 + (n / 10 - 1) * 10)) / 2;
long int sum = sum2 + sum5 - sum10;
printf("Sum is %ld", sum);
return 0;
}
실행 결과
Sum is 201
결과 검증
n = 25일 때 직접 확인해 보면 다음과 같습니다.
- 2의 배수의 합: 2 + 4 + ... + 24 = 156
- 5의 배수의 합: 5 + 10 + 15 + 20 + 25 = 75
- 10의 배수의 합(중복분): 10 + 20 = 30
따라서 156 + 75 - 30 = 201로, 프로그램의 출력과 정확히 일치함을 알 수 있습니다.