3 ms·
In 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
by biot 10y ago
In 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.