About the continuous division method learned in the 4th grade of elementary school

It has a math tag, but it's math.

Continuous division method

I learned the greatest common divisor and the least common multiple in the 4th grade of elementary school, but I learned that there is a continuous division method (both blind calculation) in the "how to do" at that time.

How to do

Greatest common divisor (GCD)

If there are divisors common to a set of integers, reduce them and multiply all the divisors to find them.

Least common multiple (LCM)

If there are two or more common divisors in a set of integers, reduce them, and multiply the divisor and the remainder to find it.

Common GCD, LCM

Of course, it can be easily done by Euclidean algorithm. Even if there are more than two pairs of integers, it can be solved with $ gcd (a, b, c) = gcd (gcd (a, b), c) $.

public int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}

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

Try to reimplement

However, since the purpose is that my daughter can reproduce it in Scratch, I will try to assemble it in Java for the time being. Source

--Try to reduce a set of integers with prime numbers

Since the method of contracting is different between GCD and LCM, Predicate is replaced. You can pass functions in Java too!

Integer primeFactory(List<Integer> intList) {
	Predicate<Integer> op = mode.equals(Mode.GCD) ? factoryAll(intList) : factoryMulti(intList);
	return primeList.stream().filter(op).findFirst().orElse(1);
}

static Predicate<Integer> factoryAll(List<Integer> intList) {
	return i -> intList.stream().allMatch(isDivisable(i));
}

static Predicate<Integer> factoryMulti(List<Integer> intList) {
	return i -> intList.stream().filter(isDivisable(i)).count() > 1;
}

――If you can make a contract, move on to the next stage

Generate a new set of integers by dividing the original set of integers by a divisor. UnaryOperator is passing unary operations. If it is not divisible by LCM, the original integer is returned.

static List<Integer> divideList(Integer divisor, List<Integer> intList) {
	return intList.stream().map(divide(divisor)).collect(Collectors.toList());
}

static UnaryOperator<Integer> divide(Integer divisor) {
	return i -> (i % divisor) == 0 ? i / divisor : i;
}

--Finally multiply all the objects

Integer getGCD() {
	return reduceDivisor();
}
Integer getLCM() {
	return getLastValue().stream().reduce(1, (x, y) -> x * y) * reduceDivisor();
}
Integer reduceDivisor() {
	return stack.stream().map(p -> p.getKey()).reduce(1, (x, y) -> x * y);
}

Afterword

There are three steps, but it seems to be difficult to build with Scratch, so it is pending. Which is the prime number derivation?