Hacker News new | past | comments | ask | show | jobs | submit login

A fairly precise raw Python translation for the interested:

    T = range(1, R)[1:]                       # T←1↓ιR
    u = [[t*u for u in T] for t in T]         # T∘.×T
    v = [t for ei, t in
          zip([any(t in ui for ui in u) for t in T], T)
         if not ei]                           # (~T∈u)/T
As the standard poem on the subject by Dave Touretzky and Don Libes says:

    I wrote some hacks in APL,
    each on a single line.
    They're mutually recursive,
    and run in n-squared time!
In this case, of course, it runs in R-cubed time, not n-squared time. There's a perhaps more common, but slightly longer, APL one-liner for finding primes that does run in O(R²) time instead; from https://aplwiki.com/SieveOfEratosthenes †:

   (2=+⌿0=(⍳X)∘.|⍳X)/⍳X
Or, eliminating the inessential variations from the above version:

   (2=+⌿0=T∘.|T)/T←⍳R
If you want APL and are stuck with Python, you can probably get most of the APL you want in Numpy. A slightly looser translation of the first algorithm into Numpy:

    import numpy

    T = numpy.arange(2, R)
    print T[~numpy.equal.outer(T, numpy.multiply.outer(T, T)
                               ).any(axis=1).any(axis=1)]
Recent versions of Numpy have numpy.isin, which works like APL ∈, which would save you the .outer.any.any nonsense.

A much more compelling demonstration of APL is, in my mind, the interactive development process leading up the the one-liner Game of Life in this livecoding video: https://www.youtube.com/watch?v=a9xAKttWgP4

† This is not the Sieve of Eratosthenes, despite the article title; the Sieve is an immensely more efficient algorithm than trial division, producing the same results in near-linear time.




I realize now that the first line should say range(1, R+1)[1:]. We regret the error.




Applications are open for YC Winter 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: