Ståle’s weblog

The third project Euler problem is about finding the largest divisor for a single number:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143

One small “problem” here is that the number 600851475143 exceeds Integer.MAX_VALUE which is 2147483647, so we have to use either Long or BigInt. I went for BigInt for this one. The algorithm I choose is pretty simple:

Take the number n, and divisor d:

• if n mod d is 0, divide n by d and check again
• if n is larger than d, increase d by 1 and check again
• d is the answer

In Scala code, the method turns out as follows:

1
2
3
4
5
6

def largestDivisor(n:BigInt, d:BigInt):BigInt = {
    if (n%d == 0) largestDivisor(n/d,d) 
    else if (n>d) largestDivisor(n,d+1) 
    else d
}
def largestDivisor(n:BigInt): BigInt = largestDivisor(n,2)

We have a convinience method here to help us out, as we always start the divisor with a value off 2. If we started with 1 we would have an endless loop, as all numbers mod 1 is 0. It’s then just a matter of printing out the result.

Again we are using tail recursion, which Scala will rewrite to a loop instead. To look at the actual result off the code, I ran the resulting class file through jad, and got the following result:

1
2
3
4
5
6
7
8
9

public BigInt largestDivisor(BigInt n, BigInt d) {
        do {
            for(; BoxesRunTime.equals(n.$percent(d), BoxesRunTime.boxToInteger(0)); n = n.$div(d));
            if(n.$greater(d))
                d = d.$plus(BigInt$.MODULE$.int2bigInt(1));
            else
                return d;
        } while(true);
    }

In line 3 we see the continual division off n/d as long as n%d == 0. This corresponds exactly to my Scala code in line 2, recursivly calling it self while dividing n by d. Line 4-7 corresponds to line 3-4 in the Scala progam, increasing d by 1 if d is less than n, or returning d. By running my Scala compiled class file through jad, I am able to exactly see how Scala converts tail recursion to loop code.

Staale Euler, Scala Euler, Math, Scala