10 to the 5=100,000 and you only have to test up to the square root and every other number, i.e. not even, which is slightly more than 150 numbers if my arithmetic is correct. So it has to be some other problem. Check any while() loops and that you are not sending the same number(s) through the test over and over.
Your original algorithm will be much too slow, for N = 1000000 you have a million calls to your function is_divisible(), and within that function you have a loop with at least sqrt(N) calculations. Even if you loop only through odd numbers that is close to a half billion calculations.
I hope you can pick something better from the python forum here. There is always module timeit to time your progress.
Python has module cProfile that can be applied to show you how many times a particular call is made and how much time it consumes.