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