Problem 5
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 by all of the numbers from 1 to 20?
This is an interesting problem. There's a few things we can tell about the answer.
All numbers are evenly divisibly by 1. If it's divisible by 2 that means it's even. If it's divisible by 20, then it's evenly divisible by 10 and 5.
Our range is 2520..?
The most obvious direction would be to start at 2520, divide by all the digits with a Boolean trigger, if false then add 20 and do it again.
There prob is an easier way but this is what I went with.
Set up the loop. I went with a while loop. I started 20 less than the starting number because if I put the increment after the bool test it will add 20 then evaluate the break criteria and the answer would be 20 more than the correct answer.
I considered a for loop and if it had been c++ I would have but I don't know that you can set up the for loop any other way than x in range and I don't know the range... While for indefinite loop, for for definite, am I right?
fn main() {
let mut found: bool = false;
let mut cur_num: i32 = 2500;
while found == false{
cur_num += 20;
found = div_cur(cur_num);
}
println!("{}", cur_num);
}
That's the main function done. I figure the actual calculation I can source out to a function for recursion.
fn div_cur(x:i32) -> bool{
let mut trigger = false;
let mut s_num = 20;
while s_num > 0{
trigger = even_div(x, s_num);
if trigger == false{
return false
}
s_num -= 1;
}
trigger
}
I considered putting some of this logic in the main while loop, and I could have but I opted to keep the math logic separate. I figured I could avoid a lot of nasty if then statements.
So this function takes in a number and returns a bool. Default return value is false. I started with 20 as a counter and am counting down. I figured that it would be quicker to divide by 20, 19, 18 than 1, 2, 3 since if it would error out it's more likely to error out on the higher divisors in range.
we check the even divide and if false there's not reason to continue. If it isn't then we're continuing the loop and so we increment. If all 20 in the divisor range return divisible it returns true.
fn even_div(x: i32, y: i32) -> bool{
return x % y == 0
}
This is function that gets called every time we want to test the division. Takes two numbers, the test number and the divisor and then returns true if it's evenly divisible and false if not.
Pretty straight forward.
Let's look at the other guys code.
Other Guy's Code
Weflown had a... different approach.
fn main() {
let mut n: u128 = 4000000;
while (n % 2) != 0 || (n % 3) != 0 || (n % 4) != 0 || (n % 5) != 0 || (n % 6) != 0 || (n % 7) != 0 || (n % 8) != 0 || (n % 9) != 0 || (n % 10) != 0 || (n % 11) != 0 || (n % 12) != 0 || (n % 13) != 0 || (n % 14) != 0 || (n % 15) != 0 || (n % 16) != 0 || (n % 17) != 0 || (n % 18) != 0 || (n % 19) != 0 || (n % 20) != 0 {
n = n + 1;
}
println!("{}", n)
}
I'm not sure where he got the 4 million starting point but that's certainly a way to do it.
According to him, "this is the worst way to do this but I don't care"
This was the only other rust response.
BitRAKE had an amazing answer and it kind of blows my mind.
This does not require programming at all. Compute the prime factorization of each number from 1 to 20, and multiply the greatest power of each prime together:
20 = 2^2 * 5
19 = 19
18 = 2 * 3^2
17 = 17
16 = 2^4
15 = 3 * 5
14 = 2 * 7
13 = 13
11 = 11
All others are included in the previous numbers.
ANSWER: 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 = 232 792 560
BitRAKE's on a whole other level.
No comments:
Post a Comment