Thursday, July 14, 2011

LCM

LCM

Once I have the prime number generator, my first usage will be for LCM calculation.
I just converted the way I used to find LCM in my school days into java code.

Enjoyed a lot sloving this cute puzzle.

Validated the results from my code @ http://www.solvemymath.com/online_math_calculator/general_math/least_common_multiple/lcm_calculator.php

import blog.prime.IntPrimeGenerator;
import java.math.BigInteger;
import java.util.Random;
import java.util.Stack;

public class LCM {
     private int[] list;
     private Stack<Integer> resultStack;
     private int allset;
     private int prime;
     private final PrimeGenerator<Integer> intPrimeGenerator = IntPrimeGenerator.integerSingletonPrime;
     public BigInteger getLCM(int[] list) {
          if(list.length ==0) throw new IllegalStateException("Input can't be empty");
          Utils.printArray(list);
          reset(list);
          BigInteger lcm = BigInteger.ONE;
          removePrimes();
          while(allset < list.length)  {
               for(int i=0;i<list.length;i++) {
                     prime = intPrimeGenerator.getNextProbablePrime(prime);
                     devideWithPrime(prime);
                     if(allset == list.length) break;
               }
          }
          while(!resultStack.isEmpty())
               lcm = (lcm.multiply(BigInteger.valueOf(resultStack.pop())));
               return lcm;
          }
     }
     private void reset(int[] list) {
        this.list = list;
        prime=0;
        resultStack = new Stack<>();
        allset = 0;
        for(int i=0; i<list.length; i++ )
            if(list[i] == 1)  allset++;
    }
    private  void removePrimes() {
        for(int i=0;i<list.length;i++)
             if(list[i] !=1 && intPrimeGenerator.isPrime(list[i])) {
                devideWithPrime(list[i]);
             }
    }
    private  void devideWithPrime(int primeNum) {
        if(allset == list.length) return;
        boolean changed = false;
        boolean primePresent =  false;
        for(int i=0;i<list.length;i++)
        if(list[i] != 1 && (list[i] % primeNum) == 0) {
            list[i] = list[i] / primeNum;
            if(list[i] == 1) allset++;
            if(intPrimeGenerator.isPrime(list[i])) primePresent = true;
            changed=true;
        }
        if(changed){ resultStack.push(primeNum); devideWithPrime(primeNum); }
        if(allset == list.length) return;
        if(primePresent) removePrimes();
    }
    public static void main(String[] args) {
        int[] localList = new int[4];
        Random rnd = new Random();
        LCM lcm = new LCM();
        for(int i=0;i<localList.length;i++) localList[i] = rnd.nextInt(Integer.MAX_VALUE - 1);
        System.out.println("Lcm :" + lcm.getLCM(localList));
        for(int i=0;i<localList.length;i++) localList[i] = rnd.nextInt(100000);
        System.out.println("Lcm :" + lcm.getLCM(localList));
    }
}
class Utils {
    public static void printArray(int... array) {
        System.out.println();
        for(int i=0;i<array.length-1;i++)  System.out.print(array[i] + ", ");
        System.out.println(array[array.length-1]);
    }
}
  


No comments:

Post a Comment