Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-24T21:17:51.286Z Has data issue: false hasContentIssue false
  • English
  • Français

FUNCTIONAL PEARL Lazy wheel sieves and spirals of primes

Published online by Cambridge University Press:  01 March 1997

COLIN RUNCIMAN
COLIN RUNCIMAN
Affiliation:
Department of Computer Science, University of York, Heslington, York YO1 5DD, UK. e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The popular method of enumerating the primes is the Sieve of Eratosthenes. It can be programmed very neatly in a lazy functional language, but runs rather slowly. A little-known alternative method is the Wheel Sieve, originally formulated as a fast imperative algorithm for obtaining all primes up to a given limit, assuming destructive access to a bit-array. This article describes functional variants of the wheel sieve that enumerate all primes as a lazy list.

Type
Research Article
Information
Journal of Functional Programming , Volume 7 , Issue 2 , March 1997 , pp. 219 - 225
Copyright
© 1997 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.