I just recently learned about Project Euler and have started doing the problems on there. I cleared problem 1 and 2, had no idea how to do 3 and 4, and started to do 5. I've seen the post regarding the quick mathematic solution, but I'd like to know if there are better ways to do it programmatically.
For those that don't know, question #5 is as follows:
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?
The logic behind my algorithm is simple:
The number in question must be divisible by all of the numbers between 1 and 20 (assume inclusive for the ranges). As a result, it must be divisible by all of the numbers between 1 and 10. The smallest number that is divisible by all the numbers between 1 and 10 (given by Project Euler) is 2520. Thus, the number in question must be a multiple of 2520. (As I'm writing this, I'm starting to question whether or not this is a necessary truth, but the program does work. Don't really want to go about proving it right now. I'm fairly certain however.) Thus, I can start at 2520 + 2520 and simply add 2520 every iteration.
It is guaranteed that these multiples will be divisible by all the numbers between 1 and 10, so there is no need to check those numbers. So I start from 11 and go to 20.
public static long problem5() {
long i = 2520;
boolean found = false;
while (!found) {
i += 2520;
boolean divis = true;
for (int j = 11; j <= 20; j++) {
if (i % j != 0) {
divis = false;
//System.out.println(i + " is not divisible by " + j);
break;
}
else {
//System.out.println(i + " is divisible by " + j);
}
}
if (divis) {
found = true;
}
}
return i;
}
I made this quick program to check my math regarding my statement "Thus, the number in question must be a multiple of 2520." It returns true if it finds a number not divisible by 2520 but divisible by all of the numbers between 1 and 10, and false if it does not find such a number. I feel that I set the limit to a reasonable limit. It indeed returns false.
public static boolean checkMath() {
int start = 2520;
int end = start * (232792560/2520);
boolean result = true;
for (int i = start + 1; i < end; i++) {
result = true;
for (int j = 1; j <= 10; j++) {
if (i % j != 0) {
result = false;
break;
}
}
if (result) {
if (i % 2520 != 0) {
break;
}
}
}
return (result);
}