Codechef: Prime Number Generator

Question

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<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= 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 " "
    i = i + 1
            

Answer 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\$.

1. 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)\$.

2. 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:

3. 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.

4. 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:

   1. 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})\$.
   2. 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.
   3. 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)\$.
   4. 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 < \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.

Answer 2

Exploit the limits. The limit is \$1 \le m \le n \le 1000000000\$, with \$t \le 10\$. Say you get 1000000000 twice you'll take forever to find the numbers. Instead if you find all the primes from 1 to 1000000000 once, then you can just loop through them, using xrange.

The simplest way to do this is to use a sieve, say the Sieve of Eratosthenes. This also has a complexity of apparently \$O(n \log\log n)\$, where yours is at minimum \$O(n^2)\$.

And so I'd use:

def sieve_of_eratosthenes(limit):
    sieve = [True] * limit
    sieve[0] = sieve[1] = False
    for i in xrange(limit):
        if not sieve[i]:
            continue
        for j in xrange(i*2, limit, i):
            sieve[j] = False
    return sieve

SIEVE = sieve_of_eratosthenes(1000000000)
def prime_between(start, stop):
    for n in xrange(start, stop):
        if SIEVE[n]:
            yield n

if __name__ == '__main__':
    n = int(raw_input())
    for _ in xrange(n):
        start, stop = map(int, raw_input().split())
        print('\n'.join(str(i) for i in prime_between(start, stop)))

Answer 3

Some quick things that caught my attention:

• Your code does not handle exceptions, what if the user inputs "xyz" and the program raises a ValueError?

• Some PEP-8 things:

  1. A comma , should be followed by a [space], for readability;
  2. A modulo operator, as well as other mathematical operators, should be preceded by and followed by a [space];
  3. A range() call (or any other function call), should not be followed by a [space] before the first argument;

• Use i += 1 instead of i = i + 1;

• Calling print without " " will also print -nothing-.

Rewritten

while True:
    x = raw_input("Input a number: ")
    if not x.isdigit():
        print("Input must be a number!")
        continue
    break

for i in xrange(x):
    a = map(int, raw_input().split())
    if a[0] == 1:
        a[0] = 2
    for num in xrange(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 
    i += 1

Answer 4

@Peilonrayz hit the point by mentioning the real problem with your implementation design which is the algorithm complexity. So I want to go further: AFAIK, the fastest known prime numbers generator algorithm is Sieve of Atkin. So you should consider this algorithm as a starting point for an effective solution for the sake of algorithm complexity.