Hostname: page-component-8448b6f56d-mp689 Total loading time: 0 Render date: 2024-04-24T13:06:24.342Z Has data issue: false hasContentIssue false
  • English
  • Français

FUNCTIONAL PEARL Calculating the Sieve of Eratosthenes

Published online by Cambridge University Press:  27 October 2004

LAMBERT MEERTENS
LAMBERT MEERTENS
Affiliation:
Kestrel Institute, Palo Alto, CA, USA and Utrecht University, Utrecht, The Netherlands (email: lambert@kestrel.edu)
Rights & Permissions [Opens in a new window]

Extract

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 Sieve of Eratosthenes is an efficient algorithm for computing the successive primes. Rendered informally, it is as follows:

1. Write down the successive “plurals”: 2, 3, 4, …

2. Repeat:

(a) Take the first number that is not circled or crossed out.

(b) Circle it.

(c) Cross out its proper multiples.

3. What is left (i.e. the circled numbers) are the successive prime numbers.

Type
Functional pearls
Information
Journal of Functional Programming , Volume 14 , Issue 6 , November 2004 , pp. 759 - 763
Copyright
© 2004 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.