3 ms·
https://stackoverflow.com/a/17189376/308851 https://stackoverflow.com/a/17189376/308851 claims it's O(N^2). 10^82 operations ... say you can run 10^10 iteration
by chx 2y ago
https://stackoverflow.com/a/17189376/308851 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.
- SushiHippie 2y agoIsn'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 2y agoFine. It's now only 10^10 times the age of the universe. much better.
- lifthrasiir 2y agoHere 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 2y agoOh. It's really not practical.