GeneratePrimes
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.
Definition
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"
"declarations"
| 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