[Algorithm/C] Project Euler. Multiple of 3 and 5

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. 

The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

#include <stdio.h>

int main(int argc, char * argv[])

{

int sum=0;

int i;

for(i=1; i<1000; i++)

{

if(i%3==0 || i%5==0)

{

sum += i;

}

}

printf("%d",sum);

return 0;

}

접근 방법

1. 3 또는 5로 나눠서 나누어 떨어지는 수를 모두 더한다.

저는 이 방법으로 처음에 생각 했는데 숫자가 커지면 커질수록 효율이 떨어지는 방법이라고 하네요.

프로젝트 오일러에서는 이렇게 제시하고 있습니다.

To get a more efficient solution you could also calculate the sum of the numbers less than 1000 that are divisible by 3, plus the sum of the numbers less than 1000 that are divisible by 5. But as you have summed numbers divisible by 15 twice you would have to subtract the sum of the numbers divisible by 15.

즉 3으로 나누어지는 모든 수의 합 + 5로 나누어지는 모든 수의 합 - 15(3과 5의 최소공배수)로 나누어지는 모든 수의 합

문제의 일반화를 시키겠습니다. 즉, 1000이 아닌 사용자 입력보다 작은 수 중 3 과 5의 배수들의 합을 구하는 코드를 프로젝트 오일러에서 제시한 방법으로 구현해보겠습니다.

#include <stdio.h>

int SumDivisibleBy(int a, int *ptr)

{

int endNum;

printf("%d : ((*ptr)-1)/a \n",((*ptr)-1)/a);

endNum = ((*ptr)-1)/a;

return a*endNum*(endNum+1)/2;

}

int main(int argc, char * argv[])

{

int input;

scanf("%d",&input);

printf("%d : Output\n",SumDivisibleBy(3,&input) + SumDivisibleBy(5,&input) - SumDivisibleBy(15,&input));

return 0;

}

이렇게 코드를 짜주면 입력이 매우커도 반복문이 없기 때문에 매우 효율적인 코드가 될 것입니다.

문제 출처 - https://projecteuler.net/problem=1