3 ms·
tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$
by delsarto 10y ago
tl;dr if you know a little regex
- convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111)
- handle 0 / 1 separately
- ^(..+?)\1+$
- trick; the WHOLE thing has to match to return (^$)
- first \1 match is "11", ergo string must be "11", "1111", "111111" to match
- second \1 match "111", ergo string must be "111", "111111", "111111111" to match
- and so on. if you find before length of string, it was not prime.
Clever trick. Look forward to being asked it in your next google interview :)
- mmagin 10y agoDoesn't this have some relation to https://en.wikipedia.org/wiki/Church_encoding https://en.wikipedia.org/wiki/Church_encoding
- loeg 10y agoIt's basically a prime sieve done on a string encoding.
- deleted 10y ago[deleted]
- biot 10y agoIn other words, it's the Sieve of Eratosthenes implemented via regex: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
- Veedrac 10y agoNo, that's completely different. This is just trial division, with really slow division.
- hexane360 10y agoWell, 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 https://en.wikipedia.org/wiki/Trial_division
- baristaGeek 10y agoFilling 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.
- aiiane 10y ago"clever trick" is something we explicitly avoid asking these days.
- bigiain 10y agoThat'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...)
- cantrevealname 10y agoThat 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.)
- posterboy 10y agoIs the applicant asked to explain the regex or to come up with the regex and the conversion to unary?