Algorithm

[Project_Euler] Multiples of 3 or 5

seandoesdev 2024. 4. 5. 08:07

Problem

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.

 

10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.

1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?

 

Java Code

public class prob_1 {
    public static void main(String[] args) {
        int a = 3;
        int b = 5;
        int c = lcm(a, b);
        
        System.out.println(geometric_series(a) + geometric_series(b) - geometric_series(c));
    }

    public static int geometric_series(int a){
        int given_number = 1000;
        int n = given_number / a;
        int an = n * a;
        
        return ((a + an) * n) / 2;
    }

    public static int lcm(int a, int b){
        return a * b / gcd(a, b);
    }

    public static int gcd(int a, int b) {
        if (b == 0) return a;
        
        return gcd(b, a % b);
    }

}

 

Python Code

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

 

 

자바는 등비수열, 최대공약수, 최소공배수를 활용해서 풀었다. given_number 변수에서 입력받는 코드로 바꾸면 1000이 아닌 어떤 수든 값을 넣어서 두 수의 각각의 배수의 합을 구할 수 있다. 

파이썬은 옛날에 했던 코드 그대로 가져왔는데, 그 당시에도 이 코드가 좋지 않다는 건 알고 있었는데 수정을 안 했네 ㅋㅋ..