# Time limit exceeded for SPOJ problem “Prime Generator”

Input

The input begins with the number $t$ of test cases in a single line ($t \le 10$). In each of the next $t$ lines there are two numbers $m$ and $n$ ($1 \le m \le n \le 1000000000$, $n-m \le 100000$) separated by a space.

Output

For every test case print all prime numbers $p$ such that $m \le p \le 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


I am trying my best to speed up this code, but I don't know any better way of doing it.

T = int(raw_input())
x= ' '
for test in xrange(T):
minim,maxim = map(int,raw_input().split())
if minim == 1:
minim += 1
for number in xrange(minim,maxim+1):
if number == 2:
print number
for i in xrange(2,number):
if number % i == 0:
break
elif i == number-1:
print number
print x

• @MukeshThawani: Your "brute-force" prime checking method is just too slow for the SPOJ contest. You need some advanced method like the Sieve of Eratosthenes, and the referenced thread shows how to do it in Python. – Martin R Nov 24 '14 at 18:54
• @MartinR I have checked it but the problem is, this algorithm works for numbers upto certain limit not for numbers of particular value to particular value, which is not the case in this question. I need to find numbers from minimum limit to maximum limit. – Mukesh Thawani Nov 24 '14 at 19:06

Disclaimer: I haven't tried the challenge myself so it will be pretty generic advices.

A bit of style

Python has a style guide called PEP 8. You'll find various tools to check that your code complies to it such as pep8, various tools to fix your code (such as autopep8). I also highly recommand testing other tools to check your code such as pylint, pychecker, pyflakes...

Problems in your code are mostly related to whitespace but you might want to get the habit of doing it right.

Also, as far as style is concerned : the x variable does not seem to be very useful (its name does not convey much meaning and the value does not change) ; the variable test is not used as such, the convention is to name throw-away values _.

A bit of scaffolding

A piece of code like the one you've submitted is quite hard to test as it is. Indeed, the only way to play with it is with input/output. This makes it quite hard to write automatic tests to ensure you do not break the algorithm but also to write performance tests to make your optimisations actually are optimisations.

Let's try to separate the concerns to have the actual algorithm on its own and the input/ouput in a different place.

Here's what I have done : the function takes a list of tuple (min, max) and returns a list of list so that each list corresponds to the list of primes. Then it is just a matter of pretty printing to solve the challenge.

I have converted the test in the example and some more to automatic tests :

def algo(input_val):
sol = []
for minim, maxim in input_val:
primes = []
if minim == 1:
minim += 1
for number in xrange(minim, maxim + 1):
if number == 2:
primes.append(number)
for i in xrange(2, number):
if number % i == 0:
break
elif i == number - 1:
primes.append(number)
sol.append(primes)
return sol

def tests():
assert algo([(1, 10), (3, 5)]) == [[2, 3, 5, 7], [3, 5]]
assert algo([(5, 100)]) == [[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]]
assert algo([(5, 100)] * 100) == [[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]] * 100
algo([(10000, 50000)])

def main():
input_val = [map(int, raw_input().split()) for _ in xrange(int(raw_input()))]
output_val = algo(input_val)
print(output_val)

if __name__ == '__main__':
tests()


Better algorithms

At the moment, algo([(10000, 50000)]) is already very slow, there is no way you'll get to the extreme values in a correct time. You'll have to improve algorithms.

Better check for primeness

At the moment, when checking whether n is prime, you consider all potential divisors up to n. It is not worth the pain at least one divisor would be smaller or equal to the square root of n.

Also, it might be worth extracting the corresponding logic in a function on its own for clarity purposes (it took me a while to understand that minim += 1 was a premature optimisation).

Once it is done, you can realise that you can do even better than this by considering only odd numbers if the number is not divisible by 2 but I won't care about this yet.

The code is already much faster and looks like :

def is_prime(n):
"""Checks if a number is prime."""
if n < 2:
return False
return all(n % i for i in range(2, int(math.sqrt(n)) + 1))

def algo(input_val):
sol = []
for minim, maxim in input_val:
primes = []
for number in xrange(minim, maxim + 1):
if is_prime(number):
primes.append(number)
sol.append(primes)
return sol


You can make it fancier by using list comprehension :

def algo(input_val):
sol = []
for minim, maxim in input_val:
sol.append([n for n in xrange(minim, maxim + 1) if is_prime(n)])
return sol


or even :

def algo(input_val):
return [[n for n in xrange(minim, maxim + 1) if is_prime(n)]
for minim, maxim in input_val
]


You can already handle much bigger values.

More tricks to handle bigger inputs

A trick to perform things quicker is to precompute values to be able to reuse them quickly. Such an algorithm for prime number is called the Sieve of Erathosthenes. You won't be able to compute it for the maximum values (n <= 1000000000) but it could be worth storing a list of primes up to sqrt(max) where max is the maximum max value in the input. If you do so, you'll perform the sieve for values up to maximum 31622 which is realistic. Then instead of checking all divisors, you can check only prime values (as primes gets rarer and rarer, I expect this to make the code faster).

Another trick might be to try to handle overlapping test cases by not performing the same actions many times.