That'd be right - a 20 year old trick becomes Google's hottest new hiring roadblock/challenge...

newsgroup comp.lang.perl.misc, October 1997. Message-ID slrn64sudh.qp.abigail@betelgeuse.wayne.fnx.com

(I don't know if abigail "invented" that, but I remember discussing it on usenet when it appeared in her .sig back in the mid/late '90s...)

In other words, it's the Sieve of Eratosthenes implemented via regex: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Well, not really. It's closer to trial division, though even that doesn't go through every single multiple from 1-n.

The difference is the sieve works on a large batch of numbers, and only tests divisibility with numbers not known to be composite, and less than sqrt(n).

https://en.wikipedia.org/wiki/Trial_division

No, that's completely different. This is just trial division, with really slow division.

Filling the Sieve has a time complexity of O(n log log n), and accessing a value is clearly O(1). This is far away from that.

That succinct explanation was excellent. Something like that should be a sidebar to the original article.

(I was curious about how it worked but didn't need a long article about the basics of RE's, prime numbers, and other things I understand well enough.)

"clever trick" is something we explicitly avoid asking these days.

Is the applicant asked to explain the regex or to come up with the regex and the conversion to unary?

Doesn't this have some relation to https://en.wikipedia.org/wiki/Church_encoding

It's basically a prime sieve done on a string encoding.