4 ms·
The precondition that you need to first convert to a unary number makes this feel like it's almost cheating. The regex is not totally trivial, but it's not sup
by isoprophlex 2y ago
The precondition that you need to first convert to a unary number makes this feel like it's almost cheating.
The regex is not totally trivial, but it's not super sophisticated either: conceptually 'just' a Sieve of Eratosthenes.
- fanf2 2y agoIt isn’t a sieve, it’s trial division. For example, a sieve skips powers of primes but this regex tests them all.
- ykonstant 2y agoCorrect, I would be much more impressed with a regex implementing the sieve of Eratosthenes. Not that this is not amusing!
- thechao 2y agoImplementing the real Sieve is quite a challenge in any language: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
- ykonstant 2y agoQuite; motivated by that paper I implemented a decent sieve of Eratosthenes with the standard wheel factorization in Lean 4: https://github.com/ykonstant1/esiv https://github.com/ykonstant1/esiv
- isoprophlex 2y agoI stand corrected :)
- fanf2 2y agoTo be fair, you aren’t alone! Matt Parker also said it’s the Sieve of Eratosthenes in his latest video.