Primes
I was working on a project Euler problem. It was finding the Largest Prime Factor of a very large number.
It was what I was working on before. I found 2 lessons from that one problem. See, I was trying to find all of the primes up to the number presented, and then select the largest one that was a factor.
As you can see, this was the cause to my problem in the previous blog where I was doing too much and killed the efficiency of the code.
The second lesson I received was, `The answer isn’t always the problem’.
See I was trying to solve for primes. I was checking to see if numbers were prime, then I would add them to the list, and retrieve the largest one.
With a bit of help I was able to solve this without going out of my way to solve for primes, they would just pop out.
That blew my mind, I am trying to find the largest prime so therefore I should use primes right?
Not in this answer.
Let me break it down.
(loop [n n
divisor 2]
(cond
(= n divisor) divisor
(= 0 (mod n divisor)) (recur (/ n divisor) divisor)
:else (recur n (inc divisor))))
Let’s begin with the 2nd conditional.
It states that if the remainder of n and divisor is 0, then to use recursion. You recurse back into itself the quotient (n / divisor) and check to see if the quotient is divisible again by the divisor. It is brilliant! 90 /3 = 3 then 30/3 = 10
The third line means if none of the conditionals are met. Start over again but with the divisor increasing by 1.
The first line is great too because, if n and the divisor are equal then it is your largest prime factor.
It is much cleaner, and simpler than my previous solution. It made the efficiency very high too, solving it in less than a hundredth of a second. I don’t know how long my previous solution would have taken.
Until next time,
Merl