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.
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.
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)?
This algorithm is not practical.