November 28th, 2012, 05:13 PM
I decided your program should be indented as
upper = round(N ** 0.5 + 0.5) # ceiling function of sqrt(N)
for m in range(2,upper+1):
if N % m == 0:
print(m, "is the smallest divisor of", N)
print(N, "is prime")
with foo as the main program.
foo repeatedly doubles k, which I think is O(log(num)).
foo calls the trial_division abomination which is runs in at worst O(sqrt(N)) time. I'd multiply the two making overall O(sqrt(num)*log(num)) time. I could be wrong.
[/code] are essential for python code!