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 (72 KB) as a gzipped postscript file.
- Slides from the symposium (119 KB) as a PDF 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.

Last modified: Fri Mar 11 20:02:37 CST 2005