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