3 ms·
> Since cubic is bigger than linear, this won't work. So it actually 'works', it's just slower.
by Yajirobe 5y ago
> Since cubic is bigger than linear, this won't work.
So it actually 'works', it's just slower.
- laszlokorte 5y agoNo, the point is that the article does not use a real regular expression: 1. Real regular expressiona can always be checked in linear time 2. primes can not be checked in linear time Ergo: primes can not be checked with regular expressions, otherwise there would be a way to check primes in linear time, which would contratict premise 2