문제 (English)
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible(divisible with no remainder) by all of the numbers from 1 to 20?
Answer: 232792560
문제 분석
최소공배수를 구하는 문제이다.
1에서 20까지의 모든 수에 대해서 나누어 떨어지는 가장 작은 수라는 것은, 1에서 20까지의 모든 수에 대한 최소공배수를 구하는 것.
최소공배수는 다음과 같이 구해진다.
- LCM(a,b) = a * b / GCD(a,b)
풀이 1
2에서 20까지 수를 증가시키면서, 최소공배수를 구한다.
LCM(최소공배수)을 구할 때 사용되는 최대공약수(GCD)는 gcd(a,b) = gcd(a, a%b)를 이용해서 구할 수 있다.
1) 2에서 20까지 i를 증가
2) i까지 구한 lcm 값에다가 i+1과의 lcm을 구하면서 전체 lcm 구한다.
코드
#[test]
fn test(){
assert_eq!(1, answer(1));
assert_eq!(2, answer(2));
assert_eq!(6, answer(3));
assert_eq!(2520, answer(10));
let s = std::time::Instant::now();
assert_eq!(232792560, answer(20));
println!("test: {:?}", s.elapsed());
}
#[cfg(test)]
// 2..=n까지에 대해 차례로 lcm 구한다.
fn answer(n: u64) -> u64{
let mut ans: u64 = 1;
for i in 2..=n {
ans = lcm(ans, i);
}
return ans;
}
#[cfg(test)]
//use the formula : gcd(a, b) = gcd(a, a%b)
fn gcd(mut a:u64, mut b:u64) -> u64{
let mut t: u64;
while b != 0 {
t = b;
b = a % b;
a = t;
}
return a;
}
#[cfg(test)]
fn lcm(a: u64, b: u64) -> u64{
let ret: u64 = a * b / gcd(a,b);
return ret;
}
풀이 2
풀이 1에서 모든 1..=20까지의 수에 대해 lcm을 구했다.
그러나, ans % i == 0의 경우는 lcm을 구할 필요 없다. 왜냐면 lcm(a,b)=a, where a%b==0
이렇게 하면 수행연산이 좀 줄어든다.
fn answer1(n: u64) -> u64{
let mut ans: u64 = 1;
for i in 2..=n {
if ans % i > 0 { // lcm(a, b) = a, where if a%b=0 따라서 0인경우 수행불필요
ans = lcm(ans, i);
}
}
return ans;
}
풀이 3
LCM을 GCD를 이용하지 않고도 구할 수 있다.
2..=7까지의 LCM을 구하는 경우를 보자.
i | 2 | 3 | 4 | 5 | 6 | 7 |
LCM | 2 | 6 | 12 | 60 | 60 | 420 |
LCM(6,4)=12가 되는 경우를 보면, i=4보다 작은 j값을 차례로 6에다 곱해보면서 i로 나눠 떨어질 때의 j가 GCD가 된다.
즉,
LCM | i | j | (LCM*j)%i | new LCM |
6 | 4 | 2 | (6*2)%4=0 | 6*2=12 |
이러한 알고리즘을 코드로 짜면 아래와 같다.
fn answer2(n: u64) -> u64{
let mut ans: u64 = 1;
for i in 2..=n{
if ans % i > 0 { // lcm(a, b) = a, where if a%b=0
for j in 2..=n { //사실 소수만을 대상으로하는것이 맞으나, 그냥해도 큰 차이는 없겠다.
if (ans * j) % i == 0 { //i=5, ans=12, j=[2,3,4,5,..]에 대해, 12*5=60만이 60%5=0이다.
ans *= j;
break;
}
}
}
}
return ans;
}
총평
최대공약수가 뭔지, 최소공배수가 뭔지를 근본적으로 생각해보게 하는 문제이다.
전체 소스코드
p5.rs
#[test]
fn test(){
assert_eq!(1, answer(1));
assert_eq!(2, answer(2));
assert_eq!(6, answer(3));
assert_eq!(2520, answer(10));
let s = std::time::Instant::now();
assert_eq!(232792560, answer(20));
println!("test: {:?}", s.elapsed());
}
#[cfg(test)]
// 2..=n까지에 대해 차례로 lcm 구한다.
fn answer(n: u64) -> u64{
let mut ans: u64 = 1;
for i in 2..=n {
ans = lcm(ans, i);
}
return ans;
}
#[cfg(test)]
//use the formula : gcd(a, b) = gcd(a, a%b)
fn gcd(mut a:u64, mut b:u64) -> u64{
let mut t: u64;
while b != 0 {
t = b;
b = a % b;
a = t;
}
return a;
}
#[cfg(test)]
fn lcm(a: u64, b: u64) -> u64{
let ret: u64 = a * b / gcd(a,b);
return ret;
}
//----------------------------------------
// lcm을 구하는 경우의 수를 줄인 버전
#[test]
fn test1(){
assert_eq!(1, answer1(1));
assert_eq!(2, answer1(2));
assert_eq!(6, answer1(3));
assert_eq!(2520, answer1(10));
let s = std::time::Instant::now();
assert_eq!(232792560, answer1(20));
println!("test1: {:?}", s.elapsed());
}
#[cfg(test)]
fn answer1(n: u64) -> u64{
let mut ans: u64 = 1;
for i in 2..=n {
if ans % i > 0 { // lcm(a, b) = a, where if a%b=0 따라서 0인경우 수행불필요
ans = lcm(ans, i);
}
}
return ans;
}
//----------------------------------------
// lcm을 구하는 것을, 원초적인 방법을 이용
#[test]
fn test2(){
assert_eq!(1, answer2(1));
assert_eq!(2, answer2(2));
assert_eq!(6, answer2(3));
assert_eq!(2520, answer2(10));
let s = std::time::Instant::now();
assert_eq!(232792560, answer2(20));
println!("test2: {:?}", s.elapsed());
}
#[cfg(test)]
fn answer2(n: u64) -> u64{
let mut ans: u64 = 1;
for i in 2..=n{
if ans % i > 0 { // lcm(a, b) = a, where if a%b=0
for j in 2..=n { //사실 소수만을 대상으로하는것이 맞으나, 그냥해도 큰 차이는 없겠다.
if (ans * j) % i == 0 { //i=5, ans=12, j=[2,3,4,5,..]에 대해, 12*5=60만이 60%5=0이다.
ans *= j;
break;
}
}
}
}
return ans;
}
끝
'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글
007. 10001st Prime (k번째 소수 구하기) (0) | 2024.08.13 |
---|---|
006. Sum Square Difference ("제곱의 합"과 "합의 제곱"과의 차 구하기) (0) | 2024.08.13 |
004. Largest Palindrome Product (가장 큰 대칭수 찾기) (0) | 2024.08.12 |
003. Largest Prime Factor (어떤 수에 대한 가장 큰 소인수 구하기) (0) | 2024.08.12 |
002. Even Fibonacci Numbers (피보나치 수 중에서 짝수 구하기) (0) | 2024.08.12 |