Skip to content

Least Common Multiple algorithm in AS3 / Java

2010 April 14

tags: AS3, Math, Programming

by Tedb0t

Today I needed to find the Least Common Multiple of more than 2 numbers for my recombinatory poem tool, and discovered it’s more of a sophisticated problem than I had initially thought. Here is my implementation, using recursive greatest common divisor reduction:

function gcd(a, b){
	// Euclidean algorithm
	var t;
	while (b != 0){
		t = b;
		b = a % b;
		a = t;
	}
	return a;
}

function lcm(a, b){
	return (a * b / gcd(a, b));
}

function lcmm(args){
	// Recursively iterate through pairs of arguments
	// i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

	if(args.length == 2){
		return lcm(args[0], args[1]);
	} else {
		var arg0 = args[0];
		args.shift();
		return lcm(arg0, lcmm(args));
	}
}

Just pass in an array like so:

trace(lcmm([1,2,3,4]));

Related Posts: