Finding the smallest positive number evenly divisible by a range of numbers

Question

This method finds the smallest positive number that is evenly divisible by all numbers from 1 to 20.

I am wondering if there is a better way to test if all iterations of a for loop completed successfully. When I put the found boolean outside the for loop, it was terminating my while loop prematurely since the break in the for loop goes to the end and executes whatever is below the for loop inside the while loop. It also seems a bit sloppy to subtract the number that is given and then add 1 to it inside the while loop. But if I put the number++ below the for loop after found is set true and I don't need to increment the number anymore. It increments one last time.

For example, for the number 20, the answer is 232792560. But due to the last increment it would return 232792561, which is an incorrect answer.

public int getLowestDiv(int n) {    
    //initialize found variable, as we havent found the number yet
    boolean found = false;
    /* initilize the number as what was passed to this method minus 1, since we will increment below*/
    int number = n - 1;

    while (found != true) {
        number++;

        for (int i = 1; i <= n; i++) {
            //for 1 to int that was passed divide the current number and see if its divisible
            if (number % i != 0) {
                break;
            } else if (i == n)
                found = true;
        }
    }
    return number; 
}

I have looked through the specs for Java's loops and didn't find anything about handling these type of situations. Specifically, I will loop for a certain number of iterations, testing if something is true, and if not, break, but only execute a particular statement if the for loop passed the condition on all iterations. I would like to see what the status-quo is when it comes to this as I've run into it before.

Answer 1

There are two parts to my initial assessment of your code.

Firstly, often the 'best' way to solve a problem where you are tempted to have a found = true type situation is to call a seperate method for that part of the work, and to simply 'return value' when you find the value... for example, your code:

     for (int i = 1; i <= n; i++) {
         //for 1 to int that was passed divide the current number and see if its divisible
            if (number % i != 0) {
             break;

         } else if (i == n)
             found = true;

     }

would be easily written as:

private static final boolean checkValue(final int value, int n) {
    while (n > 1) {
        if (value % n != 0) {
            return false;
        }
        n--;
    }
    return true;
}

then your main loop becomes:

int number = n;

while (!checkValue(number, n)) {
     number++;
}
System.out.printf("Number %d is divisible by all positive values up to %d\n", number, n);

The second issue I have is for performance..... you should not be using number++, you will save a lot of time if you only check the multiples of the largest number, so:

number += n; // instead of number++;

---

EDIT

If you look at the math, you will see that, we can do much better than number += n, and can determine that if we find a value that is a multiple of both n and n - 1 that the final result will be a multiple of that value. If we can use that value as the 'step' then we will go faster than just using n. Similarly, if we can find a multiple of all n, n - 1, and n - 2 then that would be a good step too.

So, consider the following:

private static final int checkValue(final long value, int n) {
    while (n > 1) {
        if (value % n != 0) {
            return n;
        }
        n--;
    }
    return 1;
}

This loop now returns the value at which the expression fails....

and we can use that in our main loop as follows:

    final int n = 23;

    long number = n;

    long step = n;
    int fact = n;
    int bestfact = fac;
    while (number > 0 && (fact = checkValue(number, n)) > 1) {
        if (bestfac > fact) {
            bestfac = fact;
            step = number;
        }
        number += step;
    }

    if (number < 0) {
        System.out.println("No values were found (overflow) divisible by all " + n + " factors");
    }

On my computer, the difference between this optimization and a naieve step, is 0.022ms vs 4961.271ms (or 225000 times faster!!!!!!!)