[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.