Java Reference
In-Depth Information
= gcd(3, 2)
= gcd(2, 1)
= 1
Therefore, the number of times the
gcd
method is invoked is the same as the index. We
can prove that
index
…
=
-
1.44 log
n
, where
n
fib(index
1). This is a tighter bound than
…
index
2log
n
.
Table 22.4 summarizes the complexity of three algorithms for finding the GCD.
T
ABLE
22.4
Com
parisons of GCD Algorithms
Algorithm
Complexity
Description
Listing 5.9
O
(
n
)
Brute-force, checking all possible divisors
Listing 22.3
O
(
n
)
Checking half of all possible divisors
Listing 22.4
O
(log
n
)
Euclid's algorithm
22.16
Prove that the following algorithm for finding the GCD of the two integers
m
and
n
is incorrect.
✓
✓
Check
Point
int
gcd =
1
;
for
(
int
k = Math.min(Math.sqrt(n), Math.sqrt(m)); k >=
1
; k--) {
if
(m % k ==
0
&& n % k ==
0
) {
gcd = k;
break
;
}
}
This section presents several algorithms in the search for an efficient algorithm for
finding prime numbers.
Key
Point
A $150,000 award awaits the first individual or group who discovers a prime number with at
least 100,000,000 decimal digits (
w2.eff.org/awards/coop-prime-rules.php
).
Can you design a fast algorithm for finding prime numbers?
An integer greater than
1
is
prime
if its only positive divisor is
1
or itself. For example,
2
,
3
,
5
, and
7
are prime numbers, but
4
,
6
,
8
, and
9
are not.
How do you determine whether a number
n
is prime? Listing 5.15 presented a brute-force
algorithm for finding prime numbers. The algorithm checks whether
2
,
3
,
4
,
5
, . . . , or
n - 1
is divisible by
n
. If not,
n
is prime. This algorithm takes
O
(
n
) time to check whether
n
is prime.
Note that you need to check only whether
2
,
3
,
4
,
5
, . . . , and
n/2
is divisible by
n
. If not,
n
is prime. This algorithm is slightly improved, but it is still of
O
(
n
).
In fact, we can prove that i
f
n
is not a prime,
n
must have a factor that is greater than
1
and less than or equal to
what is prime?
2
n
. Here is the proof. Since
n
is not a prim
e,
th
er
e exist two
numbers
p
and
q
such t
ha
t
n
=
pq
with 1
6
p
…
q
. Note that
n
= 2
n
2
n
.
p
must b
e
less than or equal to
n
is divisible by
n
. I
f
not,
n
is prime. This significantly reduces the time complexity of the
algorithm to
O
(
2
n
. Hence, you need to check only whether
2
,
3
,
4
,
5
, . . . , or
2
n
).
Now consider the algorithm for finding all the prime numbers up to
n
. A straightforward
implementation is to check whether
i
is prime for
i
2
=
2
,
3
,
4
, . . . ,
n
. The program is given
in Listing 22.5.
Search WWH ::
Custom Search