Codechef: Prime Number Generator Peter wants to generate some prime numbers for his cryptosystem. Help
him! Your task is to generate all prime numbers between two given
numbers!
Input
The input begins with the number t of test cases in a single line
(t&lt;=10). In each of the next t lines there are two numbers m and n (1
&lt;= m &lt;= n &lt;= 1000000000, n-m&lt;=100000) separated by a space.
Output
For every test case print all prime numbers p such that m &lt;= p &lt;= n,
one number per line, test cases separated by an empty line.
Example
Input:
2
1 10
3 5

Output:
2
3
5
7

3
5


My code
x = raw_input()

for i in range(int(x)):
    a = map(int, raw_input().split())
    if a[0] == 1:
        a[0] = 2
    for num in range(a[0],a[1]+1):
        if num == 2:
            print num
        for j in range( 2, num):
            if num%j == 0:
                break
            elif j == num - 1:
                print num
    print &quot; &quot;
    i = i + 1
I think Peilonrayz's answer is misleading (and might also timeout if you implement it): yes, you should exploit the limits, and yes, you can use the Sieve of Eratosthenes to speed things up, but not in the way he suggested. 

Let's examine the time/space complexities of a bunch of algorithms and see how they compare. Below, we'll use \$N\$ to denote the maximum of \$m\$ and \$n\$, \$D\$ to denote the maximum difference between \$m\$ and \$n\$, and \$T\$ to denote the number of test cases. For the problem at hand, \$N = 10^9\$, \$D=10^5\$, and \$T=10\$. 


OP's algorithm. Here for every input pair \$(m, n)\$, we loop over all numbers \$x\$ in this range, and check whether it is prime by checking whether it is divisible by any number between \$1\$ and \$x\$ inclusive. In the worst case, this requires time \$O(TDN)\$ and space \$O(1)\$. 
Sieve the entire range (Peilonrayz/Billal). Here we use the trick of precomputing the set of primes in the entire allowed interval of length \$N\$, which allows us to answer each input query in time \$O(D)\$. If we use a fast sieving algorithm to do this precomputation [f1] this will take time around \$O(N)\$ (suppressing small logarithmic factors). This gives us an algorithm with time \$O(N + TD)\$ and space \$O(N)\$. 


This is already a good deal faster than the original algorithm (at the cost of a lot more space). However, you can already do about as well in terms of time (and much better in terms of space) by just making some simple optimizations to OP's algorithm: 


OP's algorithm with faster primality checking. One very simple improvement to make to the original algorithm is to remove a lot of the redundant work in checking whether a number is prime. A nice "folklore" result about primality checking is that to check whether a number \$x\$ is prime, you only need to check whether it is divisible by anything less than or equal to \$\sqrt{x}\$ (if it is composite, at least one factor will be less than this). This means you can check whether each number is prime in time \$O(\sqrt{N})\$ [f2] instead of \$O(N)\$ as in the original code. This improved algorithm requires worst-case time \$O(TD\sqrt{N})\$ and space \$O(1)\$. In practice, this runs pretty fast [f3], so it will probably outperform method 2 and might be sufficient for solving this problem. 
Sieving only the relevant interval. Sieving methods like the Sieve of Eratosthenes are great, but it is important to understand why rather than apply them blindly. One reason why they are so great is that they let you eliminate many composite numbers at once very cheaply; for example, once you notice \$2\$ is prime, you can very efficiently loop over all larger even numbers and mark them as composite. 

It would be nice to do this for the interval \$[m, n]\$ without having to do it for the entire interval \$[1, N\$]. By using our earlier observation that every composite number in this range is divisible by a prime less than \$\sqrt{N}\$, we can use the following strategy:


Precompute all the primes less than \$\sqrt{N}\$ by using the Sieve of Eratosthenes. This takes time approximately \$O(\sqrt{N})\$ and space approximately \$O(\sqrt{N})\$. 
Make an empty boolean array of length \$n-m+1\$ with all values initialized to true, corresponding to the numbers between \$m\$ and \$n\$ inclusive.
For each prime in the list from 1., mark all multiples of that prime as false in the array from 2. For a prime \$p\$, this takes time \$O(D/p)\$.
The remaining values in the array set to true are the primes. Iterate over the array and print them out.


The tricky part of analyzing this is figuring out how long step 3 should take. The runtime of this step is roughly \$O(D\sum_{p &lt; \sqrt{N}}\frac{1}{p})\$, where the sum is over all primes less than \$\sqrt{N}\$. Simple bounds from harmonic series show this is at most \$O(D\log N)\$; more careful bounds from analyzing sums of reciprocals of primes show that this is actually \$O(D\log\log N)\$. (Incidentally, this is also where the \$\log\log N\$ comes from in the Sieve of Eratosthenes). 

Overall, this algorithm takes time \$O(\sqrt{N} + TD\log\log N)\$ and space \$O(\sqrt{N} + D\$), and is a clear winner for the constraints set in the problem. 


In terms of coding style advice, I think Coal_ covered a lot of the relevant points. One thing which is sometimes important for algorithmic problems in Python 2.7 is to use xrange instead of range; the main difference being that range actually stores the list in memory and can lead to increased space complexity (for example, even though your original algorithm should use space \$O(1)\$, it actually uses space \$O(N)\$ because of your use of range). 

[f1] It doesn't really matter whether we use Sieve of Eratosthenes or Sieve of Atkin; the only theoretical difference is small logarithmic terms in the complexities, and in practice it shouldn't make much of a difference for numbers of this size. 

[f2] In fact, there are very efficient primality tests which run in time and space polynomial in the logarithm of $N$. Using one of these would give you an algorithm that runs in time \$O(TD\log^{k}N)\$ and space \$O(\log^{k}N)\$ (here \$k\$ is some small integer, like 4). Theoretically this is better than the above methods (especially for large \$N\$), but the overheads from these primality tests make it not as fast as sieving for numbers this small. 

[f3] One reason for this is that not every primality check takes time \$\sqrt{N}\$; for example, the primality check catches that all even numbers > 2 are not prime in the first step. You end up saving about a $\log N\$ factor over the naive time bound.