Python finding Prime Numbers between any two numbers

Question

I'm trying to find prime numbers between any two random numbers.

Firstly, I have written the code like:

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    for j in range(2, i):
        if i%j == 0:
            break
    else:
        print i,

Now for test case suppose I enter 2, 30 then it prints

2 3 5 7 11 13 17 19 23 29

Now analyzing, we don't need to loop till "i" in second loop rather we can do same by looping till i/2, then I changed the code as:

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    for j in range(2, int(i/2)+1):
        if i%j == 0:
            break
    else:
        print i,

Then the result is same as above while we looped till i/2 in second loop.

Now, I'm trying to use the Sieve of Eratosthenes method to print the prime numbers and I used the code as:

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    sqrt_num = int(n**(0.5))
    for j in range(2, sqrt_num+1):
        if i%j == 0:
            break
    else:
        print i,

but it prints

7 11 13 17 19 23 29

for the same input.

Please help me to understand what I am doing wrong. And how I can accomplish the same using this method.

Answer 1

Your inner loop used to loop up until i-1 or i/2. This inner loop was short when i was small, and longer when i got larger.

Now, your inner loop goes up to sqrt_num, which is a constant computed from n. Difference in behavior.

Consider i = 3, the inner loop runs from j = 2 to j = 5, and will find a case where i%j == 0 ... specifically, when j == 3.

---

To be clear: the problem is "sqrt_num, which is a constant". Change it to the square root of the outer index, i.

    sqrt_num = int(i**(0.5))