Python prime generator output vs return

Question

Search python prime number generator, I found:

def primes(n): if n==2: return [2] elif n<2: return [] s=range(3,n+1,2) mroot = n ** 0.5 half=(n+1)/2-1 i=0 m=3 while m <= mroot: if s[i]: j=(m*m-3)/2 s[j]=0 while j<half: s[j]=0 j+=m i=i+1 m=2*i+3 return [2]+[x for x in s if x] print primes(13) print primes(3000) 

and:

 def get_primes(number): while True: if is_prime(number): #is_prime is defined somewhere else yield number number += 1 

Which is more efficient, return a list or yield command? What for? Think I'm looking for a very large number of primes, for example, the first 1000 primes. By the way, the second code seems like an endless loop, how to stop it?

Thank you and sorry for so many questions.

Answer 1

It really depends on what you want to do with the list of primes.

First of all, as Martijn noted, the first algorithm is a pretty smart primary sieve, and the second checks every prime number. If you are interested in fast prime algorithms, I would look for several different main screens to better understand the approach. The simplest is the Sieve of Eratosthenes.

In any case, I do not think it was your question. You are really looking for the difference between a normal Python function and a generator. There are many questions and many documentation on SO that give a good explanation of what a generator is.

This seemed in the sidebar when I looked at your question, and I think that would be useful. Or simply search for documents for the "generator".

A quick explanation is that your first function returns a list of primes up to n. Once you have this list, you can access any member of it whenever you want, call a function in the entire list, etc. The second approach is a generator. It does not return a list - it returns an iterator, which proceeds to the next premiere on demand. Therefore, if you need primes at a time to possibly call a function on each of them, an iterator can be a good one. If you need to access primes on demand, this will not be done.

If you are looking for the first number that meets some criteria, the generator is good because you do not need to specify a range. There is no reason to generate the first thousand prime numbers if you only need the first 100.

For instance:

 for prime in get_primes(2): if meets_condition(prime): return prime 

will be better than:

 primeList = primes(1000) for prime in primeList: if meets_condition(prime): return prime 

If n is small, but not if n is somewhere close to 1000.

Need to go, sorry. I will expand and verify this later. Look at generators and simple sieves!

If you are working on a projecteuler.com problem, I'm going to go ahead and suggest that the sieve will work better.