This page gives information on sieving routines, for finding primes and for factoring numbers. It includes C source code for "Robert Bennion's Hopping Sieve", which is further described in the Proceedings of ANTS III (the third Algorithmic Number Theory Symposium, June 1998, Portland, Oregon). "The hopping sieve" was developed by Robert Bennion at the University of Utah in the early 1970s. This sieve MAY have advantages over other methods if you have a small or slow cache memory.

- Slides from the symposium (71 KB) gzipped postscript file.
- BasicHoppingSieve contains files implementing a very simple version of the hopping sieve.
- ImprovedHoppingSieve contains files implementing a more complicated, but much faster version of the hopping sieve. It uses more space to eliminate the need to do remaindering operations while sieving.
- factor-sieve.c implements the "hopping-factor sieve", which efficiently factors all the numbers in an interval. This is designed to be run under a typical Unix environment.

Correspondence may be sent to
galway@math.uiuc.edu

I would very much appreciate comments on the programs provided
here. Can you re-implement them so that they show clear
advantages over other methods?

You can find much more about primes and sieving at Chris Caldwell's "The Prime Pages".

Go back to Will Galway's home page.