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 primes`

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

## 4 comments:

I am not much into python but i was wondering if you can use

len([i for i in range(2,

primes) if item%i==0])==0].using primes list instead of the value 8?

nope would not work that way. When we say

primes = [item for item in numbers if len([i for i in range(2,primes)])==0]

we are trying to use the same "primes".. I see what you are saying but the list comprehension completes execution and only then stores the result in primes. So we cannot trace back into primes and this kind of a greedy approach would not work.

To be precise, you would get a NameError complaining about "primes" not being defined.

A faster and more memory efficient way is to use "all" and the generator form of the nested comprehension as follows:

[x for x in xrange(2,10000) if all( (x%j!=0 for j in xrange(2,int(x**0.5)+1)))]

That way the inner loop quits as soon as it finds a factor.

A 2x faster way would be to skip even numbers:

[2] + [x for x in xrange(3,10000,2) if all( (x%j!=0 for j in xrange(3,int(x**0.5)+1,2)) ) ]

thanks man..that works great and is very fast from what I noticed in a short time. Great work and thanks again. I wish you made a post as non-anonymous.

Post a Comment