Java Reference
In-Depth Information
For each prime number
k
(line 17), the algorithm sets
primes[k * i]
to
false
(line 19).
This is performed
n / k - k + 1
times in the
for
loop (line 18). Thus, the complexity for
finding all prime numbers up to
n
is
n
2
n
3
n
5
n
7
n
11
-
2
+
1
+
-
3
+
1
+
-
5
+
1
+
-
7
+
1
+
-
11
+
1
c
n
2
n
3
n
5
n
7
n
11
=
O
¢
+
+
+
+
+ c
≤
6
O
(
n
p
(
n
))
n
2
n
log
n
The number of items in
the series is
p
(
n
).
=
O
¢
≤
n
n
log
n
2
This up
pe
r bound
O
¢
≤
is very loose. The actual time complexity is much better than
n
n
log
n
2
O
¢
≤
. The Sieve of Eratosthenes algorithm is good for a small
n
such that the array
primes
can fit in the memory.
Table 22.5 summarizes the complexity of these three algorithms for finding all prime num-
bers up to
n
.
T
ABLE
22.5
Comparisons of Prime-Number Algorithms
Algorithm
Complexity
Description
Listing 5.15
O
(
n
2
)
Brute-force, checking all p
os
sible divisors
Listing 22.5
O
(
n
2
n
)
Checking divisors up to
2
n
n
n
log
n
2
Listing 22.6
O
¢
≤
Checking prime divisors up to
2
n
2
n
n
log
n
Listing 22.7
O
¢
≤
Sieve of Eratosthenes
22.17
Prove that if
n
is not prime, there must exist a prime number
p
such that
p
6 = 2
n
and
p
is a factor of
n
.
✓
✓
Check
Point
22.18
Describe how the sieve of Eratosthenes is used to find the prime numbers.
Divide-and-Conquer
This section presents efficient algorithms for finding the closest pair of points using
divide-and-conquer.
Key
Point
Given a set of points, the closest-pair problem is to find the two points that are nearest to
each other. As shown in Figure 22.4, a line is drawn to connect the two nearest points in the
closest-pair animation.
Section 8.6, Case Study: Finding the Closest Pair, presented a brute-force algorithm for
finding the closest pair of points. The algorithm computes the distances between all pairs of
points and finds the one with the minimum distance. Clearly, the algorithm takes
O
(
n
2
) time.
Can we design a more efficient algorithm?
closest-pair animation on
Companion Website
Search WWH ::
Custom Search