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.
