Prime generator SPOJ problem in Python 3 I am trying to solve an SPOJ problem: print all prime numbers in a given range (as large as \$10^9\$). I have used the Sieve of Eratosthenes algorithm. But it is still slow when input is in range of \$10^4\$.

import math
no_of_cases = int(input())

for i in range(no_of_cases):
    x = input().split(" ")
    a = int(x[0])
    b = int(x[1])
    lis = set([p*i for p in range(2,b+1) for i in range(2,b+1)])


    print (sorted(set(range(a,b+1))- lis))




I have already asked a similar question over here.
I'll convert your program to a primes_below function. (I don't take into account the lower bound.)
After doing this I got:

def primes_below(n):
    lis = set([p * i for p in range(2, n + 1) for i in range(2, n + 1)])
    return sorted(set(range(2, n + 1)) - lis)


First things first, you need a maximum of \$n ^ 2\$ amount of memory.
Why?
If we look at your algorithm what is \$i_{\text{max}}\$ and \$p_{\text{max}}\$?
Both are \$n\$. And so your current largest number is \$n^2\$.

You said:


  I also tried using square root but that was throwing error.


This also wouldn't work correctly.
Lets go through every combination if we were to do that with 16.

2 * 2 = 4
2 * 3 = 6
2 * 4 = 8
3 * 2 = 6
3 * 3 = 9
3 * 4 = 12
4 * 2 = 8
4 * 3 = 12
4 * 4 = 16


This means that 4, 6, 8, 9, 12, 16 are not prime. We should know that the primes in this range are 2, 3, 5, 7, 11, 13.
And so 10, 14, 15 are all incorrectly said as prime.

But looking at the above you should be able to see that there is no point on having \$3 * 2\$, \$4 * 2\$, \$4 * 3\$.
This is as you've already done those calculations and so you should start the range for \$i\$ at \$p\$.
And this is true for your current solution.

And so we know that we should at least use:

def primes_below(n):
    lis = set([p * i for p in range(2, n + 1) for i in range(p, n + 1)])
    return sorted(set(range(2, n + 1)) - lis)


Now we need to remove the creation of numbers greater than (or equal) \$n\$.
Rather than looking at some complex maths, we'll have a look at range.


  range(stop)
  range(start, stop[, step])
  
  This is a versatile function to create lists containing arithmetic progressions.
  It is most often used in for loops. The arguments must be plain integers.
  If the step argument is omitted, it defaults to 1.
  If the start argument is omitted, it defaults to 0.
  The full form returns a list of plain integers [start, start + step, start + 2 * step, ...].
  If step is positive, the last element is the largest start + i * step less than stop; if step is negative,
  the last element is the smallest start + i * step greater than stop.
  step must not be zero (or else ValueError is raised).


This means that you can use this instead of your multiplication!

From the above we know that the first number we use is \$p * p\$, this is as \$i\$ starts as \$p\$.
The largest number we want is also \$n\$.
But we don't want to remove all the numbers that are between \$p^2\$ and \$n\$,
and so we need that step.
That step will also be \$p\$.

Or in Python:

def primes_below(n):
    lis = set([i for p in range(2, n) for i in range(p * p, n, p)])
    return sorted(set(range(2, n)) - lis)


Before we say all is good, some maths!
What is the largest \$p\$ that will mean the second range contains a value?

If \$p^2 &gt; n\$ then the second range will be empty, and so the largest \$p\$ follows the equation \$p^2 &lt;= n\$.
And so \$p_{\text{max}} = \sqrt{n}\$.

And adding this to the range significantly improves performance.

def primes_below(n):
    lis = set([i for p in range(2, int(n ** 0.5) + 1) for i in range(p * p, n, p)])
    return sorted(set(range(2, n)) - lis)


This function is roughly ~3800 times faster than the original, at n = 5000.

Now you probably think it's good enough for this challenge, it's pretty fast!
But unfortunately no. Actually I thought I'd broke my machine when I ran it the first time, and I have 32GB of RAM!
I closed every app I had on my machine and the program still broke!
This means that you have to care about the memory and your current method doesn't.

Instead we need to limit the amount of memory to \$n\$.

To do this you can use lis = [True] * n.
And then you want to change them to False if you come across one.
And you'll want to set 0 and 1 to false at the beginning.
The same way you are at the moment.
This should get you something like:

def primes_below(n):
    lis = [True] * n
    lis[0] = lis[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        for i in range(p * p, n, p):
            lis[i] = False
    return ...


Now you want to be able to return the numbers.
Python has enumerate which will give us the index and the value,
this will allow us to make a comprehension.
And so if the value is True add the index to the output.
Which will result in:

def primes_below(n):
    lis = [True] * n
    lis[0] = lis[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        for i in range(p * p, n, p):
            lis[i] = False
    return (i for i, v in enumerate(lis) if v)


Since you don't want to display some numbers you'll want to implement a lower bound, I'd do this out of the function as then if you ever need the Sieve again you'll have a 'pure' one.

This can simply be another comprehension:

numbers = (i for i in primes_below(b + 1) if i &lt; a)


And will make usage simple:

no_of_cases = int(input())
for _ in range(no_of_cases):
    a, b = map(int, input().split(" ")[:2])
    print([i for i in primes_below(b + 1) if i &lt; a)])


This however is still too slow for my liking.
And so to make it 3 times faster, at n = 10 ** 7, you can add a check if p is prime, if it is then do what we were doing before if not go to the next number.

This results in:

def primes_below2(n):
    lis = [True] * n
    lis[0] = lis[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if not lis[p]:
            continue
        for i in range(p * p, n, p):
            lis[i] = False
    return (i for i, d in enumerate(lis) if d)


This is roughly 11500 times faster than the original, at n = 5000.
And takes about 244 seconds, on my machine, to generate all the primes below 10 ** 9.