Java Reference
In-Depth Information
Let
p
(
i
) denote the number of prime numbers less than or equal to
i
. The primes under
20
are
2
,
3
,
5
,
7
,
11
,
13
,
17
, and
19
. Therefore,
p
(2) is
1
,
p
(3) is
2
,
p
(6) is
3
, and
p
(20) is
8
.
It has been proved that
p
(
i
) is approximately
i
log
i
(see
primes.utm.edu/howmany.shtml
).
For each number
i
, the algorithm checks whether a prime number less th
a
n or equal to
2
i
is divisible by
i
. The number of the prime numbers less than or equal to
2
i
is
2
i
2
i
log
i
2
i
=
log
2
Thus, the complexity for finding all prime numbers up to
n
is
2
2
log 2
2
2
3
log 3
2
2
4
log 4
2
2
5
log 5
2
2
6
log 6
2
2
7
log 7
2
2
8
log 8
2
2
n
log
n
2
+
+
+
+
+
+
+ c +
Since
2
i
log
i
6
2
n
log
n
for
i
6
n
and
n
Ú
16,
2
2
log 2
2
2
3
log 3
2
2
4
log 4
2
2
5
log 5
2
2
6
log 6
2
2
7
log 7
2
2
8
log 8
2
2
n
log
n
2
2
n
n
log
n
2
+
+
+
+
+
+
+ c +
6
n
n
log
n
2
Therefore, the complexity of this algorithm is
O
¢
≤
.
This algorithm is another example of dynamic programming. The algorithm stores the
results of the subproblems in the array list and uses them later to check whether a new number
is prime.
dynamic programming
n
n
log
n
2
Is there any algorithm better than
O
¢
≤
? Let us examine the well-known Eratosthenes
algorithm for finding prime numbers. Eratosthenes (276-194 b.c.) was a Greek mathematician
who devised a clever algorithm, known as the
Sieve of Eratosthenes
, for finding all prime num-
bers
Sieve of Eratosthenes
n
. His algorithm is to use an array named
primes
of
n
Boolean values. Initially, all
elements in
primes
are set
true
. Since the multiples of
2
are not prime, set
primes[2 * i]
to
false
for all 2
…
n
/2, as shown in Figure 22.3. Since we don't care about
primes[0]
and
primes[1]
, these values are marked
…
i
…
*
in the figure.
primes array
index
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
initial
TTTTTTTTTT T T TTT TT TTT TTTT TT
k
= 2
TTFTFT FTFT F T F TF TF TFT FT FT FT
k
= 3
TTFTFT FFFT F T F FF TF TFF FT FT FF
k
= 5
TTFTFT FFFT F T F FF TF TFF FT FF FF
F
IGURE
22.3
The values in
primes
are changed with each prime number
k
.
Since the multiples of
3
are not prime, set
primes[3 * i]
to
false
for all 3
…
i
…
n
/3.
Because the multiples of
5
are not prime, set
primes[5 * i]
to
false
for all 5
n
/5.
Note that you don't need to consider the multiples of
4
, because the multiples of
4
are also the
multiples of
2
, which have already been considered. Similarly, multiples of
6
,
8
, and
9
need
not be considered. You only need to consider the multiples of a prime number
k = 2
,
3
,
5
,
7
,
11
, . . . , and set the corresponding element in
primes
to
false
. Afterward, if
primes[i]
is
…
i
…
Search WWH ::
Custom Search