This class generates primes numbers up to a user-specified maximum.  The algorithm used is the Sieve of Eratosthenes.  Eratosthenes of Cyrene, b. c. 276 BC, Cyrene, Libya; d. c. 194 BC, Alexandria.  He was the first man to calculate the circumference of the Earth, and was also known for working on calendars with leap years and running the library at Alexandria.  The algorithm is quite simple: Given an array of integers starting at 2, cross out all multiples of 2.  Find the next uncrossed integer, and cross out all of its multiples.  Repeat until you have passed the square root of the maximum value.


Author: Alphonse

Version: 13 Feb 2002 atp.


Object subclass: #GeneratePrimes

        instanceVariableNames: ''

        classVariableNames: ''

        poolDictionaries: ''

        classInstanceVariableNames: ''

Class side

generatePrimes: maxValue

        "maxValue is the generation limit.  Returns an array of integers

        that includes all primes <= maxValue."


        maxValue >= 2 ifTrue: [   "the only valid case"


                 | s f count primes j |

                 s := maxValue.   "size of array"

                 f := Array new: s.

                 "initialize array to true."

                 1 to: s do: [ :i |

                         f at: i put: true.



                 "get rid of known non-primes."

                 f at: 1 put: false.


                 2 to: s sqrt + 1 do: [ :i |

                         (f at: i) ifTrue: [   "if i is uncrossed, cross its multiples."

                                 2 * i to: s by: i do: [ :k |

                                          f at: k put: false.   "multiple is not prime"





                 "how many primes are there?"

                 count := 0.

                 1 to: s do: [ :i |

                         (f at: i) ifTrue: [

                                 count := count + 1.   "bump count."




                 primes := Array new: count.

                 "move the primes into the result."

                 j := 1.

                 1 to: s do: [ :i |

                         (f at: i) ifTrue: [

                                 primes at: j put: i.

                                 j := j + 1.



                 ^primes.   "return the primes."

        ] ifFalse: [   "maxValue < 2"

                 ^Array new.   "return null array if bad input."


Instance side