HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Find smallest multiple

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
smallestmultiplefind

Problem

Algorithm which returns a number which is divisible by all the numbers from \$1\$ to \$n\$ without remainders.

public static void smallestMultiple(long l){
    int count = 1;
    boolean flag = true;
    while(true){
        flag = true;
        for(int i=1; i<=l; i++){
            if( count % i != 0){
                count++;
                flag = false;
                break;
            }
        }
        if(flag){
            break;
        }           
    }
    System.out.println(count);
}


Any better approach is there?

Solution

Your approach works but it is hard to read: all the logic is concentrated in the single smallestMultiple method, which is responsible for:

  • looping over the numbers



  • determining if one is divisible by all the number between 1 and l



  • printing the result



Dedicated methods

Looking at the points above, we clearly need a method whose goal will be to say if one number n is divisible by all the numbers between 1 and max.

private static boolean isDivisible(long n, int max) {
    for (int i = 2; i <= max; i++) {
        if (n % i != 0) {
            return false;
        }
    }
    return true;
}


This is very clear. It loops over all the numbers between 2 (no need to start at 1, thanks to Konrad Morawski that pointed it out) and max. If one does not divide n, then it returns false. If none were found, it means all divide n, so we return true.

Take note also of the spacing: adding a single space after the for, before the curly braces, after each semi-colon in the loop condition, greatly contributes to clarity.
long vs int

You are using inconsistently long and int. smallestMultiple takes a long as parameter but the inner loop uses an int:

//                                  vvvv
public static void smallestMultiple(long l){
    // ...
    while(true){
        //  vvv
        for(int i=1; i<=l; i++){


Also, count, which will be the result of the result is an int.

You need to clarify: what can be big enough to warrant using a long? Clearly, it is not the upper bound, which is 20 here. So l doesn't need to be a long. count, on the other hand, is expected to be big so we could use a long for this variable. In this case, it turns out that the result fits in an int, but if we increase a little the upper bound, it won't fit anymore.
Namings

  • count is a bad name here. This is really the result of the calculation. It doesn't really count anything. It is merely an temporary variable that we increment. A generic result would be more explicit.



  • l is not very clear also. We could rename it upper or max to signify that this is the upper bound for the numbers to consider.



Main method

With the above dedicated method, we then have:

public static long smallestMultiple(int max) {
    long result = 1;
    while (!isDivisible(result, max)) {
        result++;
    }
    return result;
}


With such a method, one can clearly see what is happening: we are incrementing result while it is not divisible by all the numbers from 1 to max.

Note that it also returns the result, instead of printing it: you should let whoever is calling printing the result, printing is not the task of that method.

The big advantage here: no need to break any loop and no need for flag variables: having such flags is generally a code-smell indicating that the method is doing too much.
Faster methods

There are indeed faster methods:

  • taking the prime factorization of the numbers between 1 and the `max, as shown in this answer.



  • using a property of the lowest common multiple, as shown in this answer.

Code Snippets

private static boolean isDivisible(long n, int max) {
    for (int i = 2; i <= max; i++) {
        if (n % i != 0) {
            return false;
        }
    }
    return true;
}
//                                  vvvv
public static void smallestMultiple(long l){
    // ...
    while(true){
        //  vvv
        for(int i=1; i<=l; i++){
public static long smallestMultiple(int max) {
    long result = 1;
    while (!isDivisible(result, max)) {
        result++;
    }
    return result;
}

Context

StackExchange Code Review Q#125362, answer score: 6

Revisions (0)

No revisions yet.