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

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

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

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.

Oh.

It's really not practical.