## Essay: Programming With Prime Numbers

### September 25, 2012

We introduce today a new feature of Programming Praxis: essays. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

Our first essay is about a topic dear to my heart: programming with prime numbers. The essay presents two versions of the Sieve of Eratosthenes, uses trial division to identify primes and factor composites, and provides the Miller-Rabin pseudoprime checker and Pollard rho factoring algorithm. Source code is given in five languages: C, Haskell, Java, Python, and Scheme.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.

Beautiful! This essay just made it to the required reading list in my Algorithms class. (And my Programming Language class!)

Thank you.

Outstanding paper. Thank you very much for the work.

If possible, colored syntax highlighting would be awesome for the source code!

Loving this essay format. A few more of these and you have the makings of a must-have book. So far I have spotted one error: On page 5, in the upper-right paragraph, there is an am+1 that should be a^m+1.

On page 6, “And Zhenxiang Zhang plausibly conjectures that there are no errors less than 10^3*6 when using…” I think you meant 10^36.

Question: the prime number theorem offers a very tight range for the value of the nth prime. It’s possible to check each of the numbers in that range to see which are prime in a reasonably efficient manner. If, however, the range contains multiple primes, is there any way to figure out which one is the nth?

@treeowl: Yes. See http://programmingpraxis.com/2011/08/02/the-nth-prime/.

Thank you very much for enlightening advices, I was stuck with third problem from Project Euler and then I found your clear explaination in stackoverflow, it worked very well and fast!!! Thanks again!

Paul Hofstra writes with notice of a bug in the Python version of the

`primes`

function: the first while loop should read`while p*p <= n`

. Otherwise, ifnis the square of a prime, it will be incorrectly included in the list of primes returned by the function; for instance,`primes(9)`

returns the list`[2, 3, 5, 7, 9]`

, which is incorrect. Thanks, Paul.I think there’s either a bug in the python code for rho_factors or in my understanding of same!

In the rho_factor subroutine, the check “limit == 0″ is made. Limit starts at a large number by default and is never decremented, so that test will always return False. Should it be “limit == c” instead?

No, not “limit == c”, because c gets incremented outside the “while d == 1″ loop. Perhaps some other counter that’s incremented each time the hare/tortoise step.

You’ve found a bug:

`limit`

should be decremented each time through the loop.Gah, I must be thicker than normal today. The correction (I think) should be after the “if d == n” test, when the return statement should be “return rho_factor(n, c + 1, limit – 1)”

Decrement

`limit`

in the main processing loop`while d == 1`

, after testing`if limit == 0`

; thus, the line that recomputes`t`

,`h`

and`d`

should also set`limit = limit - 1`

.