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이 아닌 어떤 수든 값을 넣어서 두 수의 각각의 배수의 합을 구할 수 있다.
파이썬은 옛날에 했던 코드 그대로 가져왔는데, 그 당시에도 이 코드가 좋지 않다는 건 알고 있었는데 수정을 안 했네 ㅋㅋ..