PrimeGenerator

 

This class generates prime numbers up to a user-specified maximum (maxValue).  The algorithm used is the Sieve of Eratosthenes.  First create an array of maxValue booleans initialized to true to indicate that the index is potentially prime.  Change the first element to false since 1 is not prime.  Next loop through the array looking for a prime index (e.g., 2).  Generate multiples of that number (e.g., 4, 6, 8) up to maxValue and change the array value there to false since multiples are not prime.  Repeat until reaching the square root of maxValue.  Lastly collect the indexes of elements in the array which are still true, since they are prime.

Definition

Object subclass: #PrimeGenerator

        instanceVariableNames: ''

        classVariableNames: ''

        poolDictionaries: ''

        classInstanceVariableNames: ''

Class side

findPrimes: aBooleanArray

 

        ^aBooleanArray selectKeys: [ :each | each ].

 

generatePrimes: maxValue

 

        ^maxValue >= 1 ifTrue: [

                 self findPrimes: (self siftPrimes: (self initPrimes: maxValue)).

        ] ifFalse: [

                 Array new.

        ].

 

initPrimes: maxValue

 

        ^(Array new: maxValue) atAllPut: true;

                 atFirstPut: false;

                 yourself.

 

siftPrimes: aBooleanArray

 

        | maxPrimeFactor |

        maxPrimeFactor := aBooleanArray size sqrtFloor.

        1 to: maxPrimeFactor do: [ :baseIndex |

                 (aBooleanArray at: baseIndex) ifTrue: [

                         2 * baseIndex to: aBooleanArray size by: baseIndex do: [ :multipleIndex |

                                 aBooleanArray at: multipleIndex put: false.

                         ].

                 ].

        ].

        ^aBooleanArray.

Instance side