Python coding, nested loops

Question

Assume there are two variables, k and m, each already associated with a positive integer value and further assume that k's value is smaller than m's. Write the code necessary to compute the number of perfect squares between k and m. (A perfect square is an integer like 9, 16, 25, 36 that is equal to the square of another integer (in this case 3*3, 4*4, 5*5, 6*6 respectively).) Associate the number you compute with the variable q. For example, if k and m had the values 10 and 40 respectively, you would assign 3 to q because between 10 and 40 there are these perfect squares: 16, 25, and 36,.

**If I want to count the numbers between 16 and 100( 5,6,7,8,9 =makes 5)and write code in terms of with i and j, my code would be as follows but something goes wrong. I want to get the result,5 at last. how can I correct it?

 k=16
 m=100
 i=0
 j=0
 q1=0
 q2=0
 while j**2 <m:
 q2=q2+1
 while i**2 <k:
 q1=q1+1
 i=i+1
 j=j+1
 print(q2-q1)

Answer 1

Your probably don't want to loop for this. If k and m are very far apart it will take a long time.

Given k < m, you want to compute how many integers l such that k < l^2 < m. The smallest possible such integer is floor( sqrt(k) +1 ) and the largest possible such integer is ceil(sqrt(m)-1). The number of such integers is:

import math
def sq_between(k,m):
 return math.ceil(m**0.5-1) - math.floor(k**0.5+1) +1

This allows for

sq_between(16,100)

yielding:

5

• quant: This results in "NameError: name 'sq_between' is not defined" for me ... Same for "math.sq_between(0, 100)" ... Tried with both python 2 and pyhton 3 ...
• Christian Sloper: the code defines sq_between, thats what the "def" does.

Answer 2

Here is another version of your function that seems to do to what you ask for.

k = 16
m = 100
perfect_squares = []
for i in range(m):
 if i**2 < k:
 continue
 if i**2 > m:
 break
 perfect_squares.append(i**2)
print(perfect_squares)

Answer 3

You code is mixing up everything in the second while loop. If you explain a bit further what you are trying to do there, I will probably be able to explain why your idea is not working.

I would change your code as follows in order to make it work:

k = 10
m = 40
i = 0
q = 0
while i ** 2 < m:
 if i ** 2 > k:
 print(i)
 q += 1
 i += 1
print (q)

By utilizing the fact that each square number can get expressed via square = sum from i = 1 to n (2 * i + 1) there is an easy way of speedup the above algorithm - but the algorithm will become much longer then ...