Below is possibly the world's simplest Python generator: it's a function that includes the

`yield`

statement in a loop. It takes a number as the single argument and increments it once for each pass through the loop. The loop is endless: `while True`

, but that's not a problem because we ask for one value at a time. Eventually we tire of the game and kill the process.Notice that if we really wanted the test to work properly, we should reverse the order of the statements in the second while loop.

We can extend this idea to the problem of finding prime numbers---one of the oldest computational problems. In the code below we cache and then serve up the first four values. After that, the algorithm is that we test each prime number p in turn against the candidate n:

first, construct p*p

if p*p == n, n is not prime, it's the square of a prime

elif p divides n evenly, n is not prime

elif p*p > n, n is prime

else: test the next p

If n passes all the tests, it joins the club. Since all the primes beyond 5 end in 1, 3, 7, or 9, we test no other candidates.

I did three runs, a short one with v (verbose) = True to help test our logic, and longer ones with N = 10000 and N = 100000.

We grab N primes and look at the distribution.

Notice that the probability of ending in 1, 3, 7, or 9 is essentially identical. It would be interesting to look at the patterns in more detail, for example within a particular decade do 3 and 7 tend to cluster, etc.

It's seems likely that this is not efficient. The tests for 2 and 3 seem unnecessary. We should just test whether n is even, whether the sum of the digits is divisible by 3, and never test 5 at all. There are other divisibility rules as well (wikipedia).

If you want an efficient prime number generator in Python, go here. Although unutbu is awesome, you should look at Alex Martelli's answer, which is short and awfully fast.

[UPDATE: I found several errors in an earlier version of this post.]

## No comments:

Post a Comment