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