No Permission

When I first read Problem 3 I thought it was going to be more involved than it turned out to be.

“What is the largest prime factor of the number 600851475143 ?”

And I started thinking I’ll need to list the factors and test them for primality, or find primes first and test only those for being factors, etc.

But after thinking about how to actually factor the number, I remembered factor trees and how they’d lead me to prime factors by default. And as an added bonus, factor trees are inherently recursive! This wasn’t going to be so bad after all.

For some reason I got hooked on the idea that I needed to build a list of the factors, and then at the end I would find the largest of them. Eventually I realized I just needed to track the largest so far; I think I just wanted to fiddle with lists in Erlang.

The Erlang came pretty easy to me this time. I’m adjusting to the structures imposed by Single Assignment, which was conceptually a challenge at first. The idea of immutable variables just seemed so wrong! But I’ve read more and understand why that’s the case and I’m getting a feel for how to deal with them.

The only real Erlang catch came from the line that finds the co-factor of the most recently found factor – “Cofactor = round(N / Factor)”. You’ll notice the “round” function there. The division returned a floating point number, when what I wanted was an integer. Casting variable types turns out to be a bit clunky in Erlang, mostly done by BIFs (Built In Functions) with unwieldy names like “integer_to_list” and so on. But there is no “float_to_integer” BIF! So it had to be the “round()” function. While fine in this case, I’m not sure this will always do what I need it to do.

A couple of other notes- This isn’t very optimized, I’m intentionally not optimizing in this initial pass. I do plan to revisit and refactor down the road, once I have a better idea what I’m doing. I did sneak in an optimization in the factor search, limiting the upper end to the square root of the number we’re looking for factors of. That’s a very simple trick which does save some iterations (if you haven’t found a factor by the time you reach the square root of a number, you’re not going to). I could have further limited the search range by limiting the lower end to being equal to or greater than the previously found factors, but that would add parameters to the functions so I skipped it for now.

One last thing, the program doesn’t seem to work properly on very large numbers (giving me a factor of “2″ on numbers that aren’t even, for example), I’m not sure why. Probably some sort of overflow condition.

My code of codes-

 -module(euler3).
  -import(math).
  -export([greatestprimefactor/1]).

  greatestprimefactor(N) ->
     Greatest = factor(1,N),
     io:format("GPF is ~w~n", [Greatest]).

  factor(Greatestsofar,N) ->
    Max=math:sqrt(N),
    Factor = nextfactor(Max,2,N),
    if
      Factor > Greatestsofar ->
            Newgreatest = Factor;
      true ->
            Newgreatest = Greatestsofar
    end,
    Cofactor = round(N / Factor),
    io:format("Factor ~w~n",[Factor]),
    if
      Cofactor == 1 ->
           Newgreatest;
      true->
           factor(Newgreatest,Cofactor)
    end.

 nextfactor(Max,X,N)->
      if
       N rem X == 0 ->
 	    X;
       X =< Max ->
            nextfactor(Max,X+1,N);
       true ->
            N
       end.