|
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. |