Q.
10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.
1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?
A.
3의 배수의 합과 5의 배수의 합에서 최소공배수의 합을 뺀다.
#include
int main()
{
int a = 3, b = 5, max = 1000;
int sum3=0, sum5=0, cross=0;
int i, j, k;
for( i = 1; a * i < 1000; i ++ ) {
sum3+=a*i;
}
for( j = 1; b * j < 1000; j ++ ) {
sum5+=b*j;
}
for( k = 1; a * b * k < 1000; k ++ ) {
cross+= a*b*k;
}
printf("%d\n", sum3+sum5-cross);
return 0;
}
그냥 단순하게 하면 이처럼 해도 되지만, 1~n까지의 합을 다음과 같이 구하는 것이 조금 더 효율적이다.
단, 최소공배수인 15는 이미 알고있다고 가정한다.
1~n까지 연속된 수의 합은 n * ( n+1 ) / 2 이므로, 각 배수의 합은 여기에 해당 값을 곱하면 된다.
#include
int main()
{
int Cnt3 = 0, Cnt5 = 0, Cnt15 = 0;
int sum3 = 0, sum5 = 0, sum15 = 0;
int max = 1000;
Cnt3 = max / 3;
Cnt5 = max / 5;
Cnt15= max / 15;
sum3 = ( Cnt3 * ( Cnt3 + 1 ) / 2 ) * 3;
sum5 = ( Cnt5 * ( Cnt5 + 1 ) / 2 ) * 5;
sum15 = ( Cnt15 * ( Cnt15 + 1 ) / 2 ) * 15;
printf("%d\n", sum3 + sum5 - sum15);
return 0;
}
위를 일반화 시키면 다음과 같다.
프로그램 실행 시, 해당하는 인자값을 받도록 수정하였다.
사용 : 실행파일 [인자1] [인자2] [제한값]
#include <stdio.h>
int getLCM(int left, int right); // 최대공약수를 반환하는 함수
int getGCD(int left, int right); // 최소공배수를 반환하는 함수
int getCntInRange(int num, int range); // 범위내 인자의 배수 갯수를 반환하는 함수
int getSumInRange(int num, int range); // 범위내 인자의 배수 합을 반환하는 함수
int main(int argc, char* argv[] )
{
int paramCnt = argc;
if( argc != 4 )
{
printf("사용법 : [실행파일명] [첫번째수] [두번째수] [제한값]\n");
return -1;
}
int lcm = 0;
int left = atoi(argv[1]); // 문자열 인수를 숫자로 변환
int right = atoi(argv[2]);
int max = atoi(argv[3]);
lcm = getLCM( left, right );
printf("%d\n", getSumInRange( left, max )
- getSumInRange( right, max )
- getSumInRange( lcm , max ) );
return 0;
}
int getLCM(int left, int right)
{
return left*right/getGCD(left,right); // 두 인자의 곱에서 최대공약수로 나누면, 최소공배수가 나온다.
}
int getGCD(int left, int right)
{
int temp = 0; // 유클리드 호제법에 의해 최대공약수를 구한다.
while(right)
{
temp = left % right;
left = right;
right = temp;
}
return left;
}
int getSumInRange(int num, int range)
{
int cnt = getCntInRange(num, range);
return cnt * ( cnt + 1 ) / 2 * num; // n까지의 자연수 합에 인자값을 곱하여, 범위 내 인자값의 배수 합을 구한다.
}
int getCntInRange(int num, int range)
{
return range / num;
}
