3 ms·
It isn’t a sieve, it’s trial division. For example, a sieve skips powers of primes but this regex tests them all.
by fanf2 2y ago
It 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.