2 또는 5로 나누어 떨어지는 n개의 자연수의 합은 2로 나누어 떨어지는 N까지의 모든 자연수의 합과 5로 나누어 떨어지는 N까지의 모든 자연수의 합을 구하여 구할 수 있습니다. 이 두 합을 더하면 그런 다음 10으로 나눌 수 있는 N까지의 자연수의 합으로 빼면 원하는 결과가 나옵니다. 이 방법은 n의 큰 값까지 합을 찾는 데 사용할 수 있는 효율적인 방법입니다.
루프와 조건문을 사용한 다음 2 또는 5로 나눌 수 있는 모든 숫자를 추가하는 방법을 생각하는 사람도 있을 것입니다. 그러나 이 방법은 n차의 시간 복잡도를 갖기 때문에 비효율적입니다. 이것은 n의 큰 값에 대해 프로그램이 루프를 n번 실행한다는 것을 의미합니다. 그리고 이 실행은 프로그램을 무거워지게 할 것입니다.
2로 나누어 떨어지는 n개의 자연수의 합을 구하는 공식
Sum2 = ((n / 2) * (4 + (n / 2 - 1) * 2)) / 2
5로 나누어 떨어지는 n개의 자연수의 합을 구하는 공식
Sum5 = ((n / 5) * (10 + (n / 5 - 1) * 5)) / 2
10으로 나누어 떨어지는 n개의 자연수의 합을 구하는 공식
Sum10 = ((n / 10) * (20 + (n / 10 - 1) * 10)) / 2
원하는 출력
Sum = Sum2 + Sum5 - Sum10
예시
#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 %d", sum);
return 0;
} 출력
Sum is 201