[tholman]

Fun hypothetical, or can someone solve? How long, would this regex prime check [1] (via hn 2009) take to run on this on todays average machine?

Hitchhiker's Guide's Deep Thought "42" was 7.5 million years, just for a guide-post.

- [1] https://news.ycombinator.com/item?id=707236

[chx]

https://stackoverflow.com/a/17189376/308851 claims it's O(N^2). 10^82 operations ... say you can run 10^10 iterations in a second which no current CPU is capable of but let's pretend, it's not like a factor of 10 or 100 will make a big difference given how this is like 10^54 times the age of universe.

This algorithm is not practical.

[lifthrasiir]

Here N should be interpreted as the number itself, not the number of digits (in any base). So the actual complexity is exponential in terms of the number of digits and in fact it will take about 10^(10^8) times the age of universe to build the string alone.

[chx]

Oh.

It's really not practical.

[SushiHippie]

Isn't it basically this algorithm + overhead from using strings/regex?

  def is_prime(n):
    if n < 2:
      return False
    for i in range(2, int(n ** 0.5) + 1):
      if n%i==0:
        return False
    return True

Haven't tested this, just quickly jotted it down in the HackerNews textarea, but theoretically it should be python code, which checks if n is divisible by any number between 2 and sqrt(n).

And wouldn't this algorithm be just O(n), what does the regex engine do differently (except the string overhead)?

[chx]

Fine. It's now only 10^10 times the age of the universe. much better.

[lifthrasiir]

Heavily depends on how sophisticated are regex engines. Regex engines are like compilers, in that they are free to do anything as long as the result doesn't change (in a certain defined manner, of course), so engines can of course specialize for that particular regex. They don't even have to specially target the non-prime regex (yes, that matches 0, 1 or n*m copies of ones where n, m >= 2) by the way, because backreferences are already pretty rare and there are lots of potential optimizations to be made if they were much more popular. So the answer can greatly vary even when we limit ourselves to contemporary libraries. That said, it would be extremely more impractical to build a string made of 2^136279841 - 1 ones to run that regexp.

(Seriously though, it would make a very good April fools' day PR to recognize that particular regex and trigger a non-trivial prime check routine to match them.)