APL Hacking; Project Euler (#27)
Wednesday, April 20, 2011 2:37:09 AM
∇Z←PETWENTYSEVEN;A;B;X;P ⍝ Find the product of the coefficients A and B ⍝ that have the longest consecutive n values from 0 ⍝ for the quadratic formula. ⍝ P is the prime table used by CONS∆PRMS. ⍝ Seed it with the primes we use for B since we compute ⍝ those anyways. P←(2=+⌿0=(⍳1000)∘.|⍳1000),17000⍴¯1 ⍝ Use the full range for A A←(⌽-⍳1000),0,⍳1000 ⍝ We only need to use the primes for B B←(⌽-B),0,B←P[⍳1000]/⍳1000 X←,A∘.CONS∆PRMS B Z←((⌈/X)=X)/,A∘.×B ∇ ∇N←A CONS∆PRMS B;R;⎕IO ⎕IO←1 ⍝ Given (N*2)+(A×N)+B, how many consecutive values of N ⍝ starting at N=0 result in primes? ⍝ Assume a global P that stores the primality of each ⍝ value R, where P[R] is as follows: ⍝ ¯1 Uninitialized ⍝ 0 Not prime ⍝ 1 Prime N←¯1 LP:N←N+1 ⋄ R←|(N*2)+(A×N)+B ⍝ Grab the memoized result if available, →(0=R)/0 ⋄ →(0=P[R])/0 ⋄ →(1=P[R])/LP ⍝ Memoize the result, otherwise. →(P[R]←2=+/0=(⍳R)|R)/LP ∇
I did some profiling on this one to discover that the prime number table is actually best done with a small amount of initial primes, because the table ends up being a little sparse, and you don't want to waste time doing the prime computations if you don't have to.
Of course, having the prime table at all basically doubles the speed of the program. The biggest inefficiency now is the search for the highest prime N in the CONS∆PRMS function. I think I could do better if I did some sort of shortcutting or found some sort of mathematical property that let me reduce the search, but unless I find something like that, the looping there accounts for over 60% of the total running time.