Saturday, October 18, 2014

Calculating LCM of N numbers (Using Common Factors Grid Method)

This program calculates LCM of n numbers. It uses the Common Factors Grid method.

There are more ways to calculate LCM : http://www.wikihow.com/Find-the-Least-Common-Multiple-of-Two-Numbers.

You might want to check out Euclid's algorithm for finding the LCM of two numbers.

Algorithm used in this Code:

1. Find the smallest number in the numbers given.
2. Starting from 2 (upto the number itself) find a number that divides the smallest number fully.
3. Use this number to divide all the numbers in consideration that are divisible by it.
4. When all the elements have been divided down to 1, we have calculated the LCM.

Code:

import java.util.Arrays;

public class LCM {

    private static double LCM = 1;

    private static int returnMinValue(int[] array) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; ++i) {
            if (array[i] != 1 && array[i] < min) {
                min = array[i];
            }
        }
        return min; //When this returns Integer.MAX_VALUE, we are done
    }

    private static int returnFirstDivisor(int val) {
        if (val == Integer.MAX_VALUE) {
            return -1; //Return -1 to signal end
        } else {
            for (int i = 2; i <= val; ++i) {
                if (val % i == 0) {
                    LCM *= i;
                    System.out.print(i+" ");
                    return i;
                }
            }
        }
        System.err.println("Unnecessary return!");
        return -10;
    }

    public static void main(String[] args) {

        //Your numbers here
        int array[] = new int[]{9, 14, 21, 99};

        while (true) {
            int minDivisor = returnFirstDivisor(returnMinValue(array)); 
            if (minDivisor == -1) break; 
            
            for (int i = 0; i < array.length; ++i) {
                if (array[i] % minDivisor == 0) {
                    array[i] /= minDivisor;
                }
            }
            System.out.print(Arrays.toString(array)+"\n");
        }
        System.out.println("LCM = " + LCM); 
    }
}
 
Output: 
3   [3, 14, 7, 33]
3   [1, 14, 7, 11]
7   [1, 2, 1, 11]
2   [1, 1, 1, 11]
11   [1, 1, 1, 1]
LCM  =  1386.0

No comments:

Post a Comment