One year, 41M digits: How Luke Durant found the largest known prime number

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

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.

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)?