Find smallest multiple

Question

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?

Answer 1

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.

Answer 2

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;
    }           
}

If, at the moment you change flag, we need to break;, or if you don't change flag, you need to break; as well, why do you have flag at all? Or a while loop?

public static int smallestMultiple(long l){
    int count = 1;
    for(int i=1; i<=l; i++){
        if( count % i != 0){
            count++;
            return count;
        }
    }
    return count;
}

But looking at this code... it seems you will either return 1 or 2. Never any other number. So I think you've got broken code...

Answer 3

You're asking for a program which computes the least common multiple of 1, 2, 3, ..., n. You can do this with recursion:

// Compute lcm(1, 2, 3, ..., n-1, n).
public static void smallestMultiple(long n) {
  if (n < 3) return n;
  return lcm(smallestMultiple(n-1), n);
}

public static long lcm(long m, long n) {
  // Note: divide before multiplying to avoid overflow.
  return (m / gcd(m, n)) * n;
}

// Computes the greatest common divisor by Euclid's algorithm
public static long gcd(long m, long n) {
  if (m == 0) return n;
  if (n == 0) return m;
  return gcd(n, m%n);
}

You might consider binary splitting, which avoids large numbers until the end. For this problem it's not too important, but this approach would be much faster if your inputs were large and you were using bignums.

// Compute lcm(1, 2, 3, ..., n-1, n).
public static void smallestMultiple(long n) {
  return lcmRange(2, n);
}

// Compute lcm(lower, lower+1, ..., upper-1, upper).
public static long lcmRange(long lower, long upper) {
  long diff = upper - lower;
  if (diff > 2) {
    long mid = lower + diff/2;
    return lcm(lcmRange(lower, mid), lcmRange(mid+1, upper));
  }
  if (diff == 2) return lcm(lower, upper);
  return lower;
}

// Reduce least common multiple to greatest common divisor.
public static long lcm(long m, long n) {
  // Note: divide before multiplying to avoid overflow.
  return (m / gcd(m, n)) * n;
}

// Computes the greatest common divisor by Euclid's algorithm
public static long gcd(long m, long n) {
  if (m == 0) return n;
  if (n == 0) return m;
  return gcd(n, m%n);
}

Prime factorization works even better: take the product of all primes from 2 to n, times the product of all the primes from 2 to sqrt(n), times the product of all the primes from 2 to cbrt(n), etc. This is pretty fast if done recursively as above.

Of course since your code overflows for n > 43 you could also just hardcode the first 43 values:

private static long[] smallestMult = { 1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, 27720, 27720, 360360, 360360, 360360, 720720, 12252240, 12252240, 232792560, 232792560, 232792560, 232792560, 5354228880, 5354228880, 26771144400, 26771144400, 80313433200, 80313433200, 2329089562800, 2329089562800, 72201776446800, 144403552893600, 144403552893600, 144403552893600, 144403552893600, 144403552893600, 5342931457063200, 5342931457063200, 5342931457063200, 5342931457063200, 219060189739591200, 219060189739591200, 9419588158802421600};

// Return lcm(1, 2, 3, ..., n-1, n).
public static void smallestMultiple(long n) {
  return smallestMult[n-1];
}