APL Hacking: Project Euler Daily (#3)

For this problem, I had originally computed a very slow and annoying algorithm until I realized that computing the prime factors meant literally what I used to do in grade school. That simplified things down since I could grow a list of primes while at the same time shrinking the large value of N, which is too large to sit in 32-bit integers, and makes a Sieve too impractical to implement.

Problem #3:

∇R←PETHREE;N;P;X;⎕IO
⎕IO←1
⍝ What is the largest prime factor of 600851475143
N←600851475143
⍝ We will compute the prime factors by growing a list of primes.
⍝ P Primes

⍝ X Factor under consideration

⍝ N Number to factor
P←2 ⋄ X←3
LOOP:→(0∊P|X)/CONT ⋄ P←P,X ⋄ →(0≠X|N)/CONT

SHRINK:N←N÷X ⋄ →(0=X|N)/SHRINK

CONT:X←X+2 ⋄ →(X<N)/LOOP
R←N

∇

Extended explanation

Prime factors of a given number are the factors of a number that are prime. You did this in grade school when you factored numbers into their prime factors by first checking if it was divisible by two, then three, and so forth. Each time you found a factor, you would see how many of those you could use before moving on to the next prime. So, take 56 for example:

56 = 2 × 28

= 2 × 2 × 14

= 2 × 2 × 2 × 7

Now, at this point, 7 is a prime, and that is the last one.

The algorithm above does the exact same thing. It keeps track of the prime numbers in an array P that starts with 2. X start at 3 and increments by two. For each X, we check whether it is a prime factor, and if it is, we divide our current N by it, setting the quotient to be our new N. We repeat this until X no longer divides N, in which case we continue with X added to the list of primes and X containing the next number to test for primality.

The LOOP label line checks for prime factor, the SHRINK line is the line that shrinks or divides the N until it is not possible to do so, and the CONT line continues by incrementing the X value and checking whether we have reached the end. We know that we have reached the end when our X is greater than or equal to N.

The main trick here is the APL one armed conditional jump idiom.

→(0∊P∣X)/CONT

These types of forms are jumps where the → will jump to whatever label is to its right, unless there is nothing to its right, in which case it continues. In the above, we test whether X is divisible by any of our primes, thus making it non-prime, and allowing us to skip the rest of the computation and move to continue the loop. That (...) will be 0 or 1, where the 0 will cause the / to not select its single left argument, and the 1 will cause / to select the CONT.