1: inp = int(raw_input('Enter the outer bound : '))
2: l = range(1,inp)3: #factors = [i for i in range(2,item/2+1) if item % i == 0]
4: primes = [item for item in l if item>1 and len([i for i in range(2,item/2+1) if item % i == 0])==0]
5: print primesThe code could further be optimized to improve the performance drastically.
1: primes=[item for item in l if item>1 and len([i for i in range(2,8) if item%i==0])==0]
Notice that I am using list comprehensions and in the inner list comprehension inside the len() I am limiting the range of divisors to 8. Obviously any number greater than 8 would be divisible by one of the numbers between 2 and 8 (if it is a composite number).
The above optimized version is fast – so fast that to compute the list of primes between 1 and 50000, it just takes at most a second (did not time it actually) whereas the first one takes forever (i completed typing the whole paragraph and it is still running!). So I verified it with a range from 1 to 5000 and the first one is almost instantaneous.
But! there is a bug in the second algorithm that i listed. It does not verify those numbers that are divisible by other prime numbers which are not between 2 and 8. So any ideas to optimize this?
Basic algorithm: return all items in a list whose length of the factors list is 0.
Where is the place for optimization?
Computing the factors! is the key here. The faster you compute your factors, the better your algorithm would perform.