4 ms·
Nice (abuse of regexp) ! AFAICT the way the string is going to be parsed is equivalent to this: def isprime(n): if n == 0 or n == 1: return False
by charlesacknin 12y ago
Nice (abuse of regexp) !
AFAICT the way the string is going to be parsed is equivalent to this:
def isprime(n):
if n == 0 or n == 1:
return False
i = 2
while i <= n:
if (n - i) % i == 0:
return False
i += 1
return True
A parser implementation may optimize and do "while (n - i) >= 1" instead, which cuts in half the number of iterations.
- jdmichal 12y agoA better implementation will only check to sqrt(n), as there can be no prime factor greater than that.
- punee 12y agoYes, there can.
- tom-lord 12y agoThe point is that if there is a prime factor greater than sqrt(n), then your will have already found its co-factor by then.
- jdmichal 12y agoCorrect. I misspoke. I should have said, A better implementation will only check to sqrt(n), as there can be no prime factor greater than that without there also being a prime factor lower than that.