created 01/01/03

# Chapter 72 Programming Exercises

## Exercise 1

A prime number is an integer that cannot be divided by any integer other than one and itself. For example, 7 is prime because its only divisors are 1 and 7. The integer 8 is not prime because its divisors are 1, 2, 4, and 8.

Another way to define prime is:

```prime(N)    = prime(N, N-1)

prime(N, 1) = true

prime(N, D) = if D divides N, false
else prime(N, D-1)
```

For example,

```prime(4)   = prime(4,3)
prime(4,3) = prime(4,2)
prime(4,2) = false
```

Another example,

```prime(7)   = prime(7,6)
prime(7,6) = prime(7,5)
prime(7,5) = prime(7,4)
prime(7,4) = prime(7,3)
prime(7,3) = prime(7,2)
prime(7,1) = true
```

Translate the math-like definition of prime into two Java methods that return `boolean`. Use the `%` operator to test divisibility. Put your method into a class, write a testing class, and test your program. (Look at `FactorialTester.java` in this chapter.)

If you run your program for integers larger than about 12,000 (on a Windows system) you will run out of memory. Your program will stop running and report a StackOverflowError. This is because each activation in the activation chain requires some memory, and 12,000 activations uses up all the memory that has been reserved for this use.

This is not a good method for finding primes. If you really want to compute primes, use the Sieve of Eratosthenes.

## Exercise 2

Assume that female rabbits live for only 4 months. Modify the math-like definition of the Fibonacci series to account for dying rabbits. Implement the new series as a Java method.

First draw a chart showing the population of rabbits by month. Then deduce the new rules for the series. You will have more base cases than in the original series.

## Exercise 3

The greatest common divisior GCD of two integers `a` and `b` is the largest integer `k` that divides both `a` and `b` evenly. (That is, `k` divides both `a` and `b` without leaving a remainder.)

For example, `GCD( 6, 9 ) == 3` because 3 evenly divides both 6 and 9 and no greater integer does so. Another example, `GCD( 25, 55 ) == 5`.

Here is a math-like definition of GCD:

```GCD(0,N) = N

GCD(A,B) = GCD( B%A, A )     % is the remainder after integer division B/A
```

For example,

```GCD( 6, 9 ) = GCD( 9%6, 6 ) = GCD( 3, 6 )
GCD( 3, 6 ) = GCD( 6%3, 3 ) = GCD( 0, 3 )
GCD( 0, 3 ) = 3
```

Translate the math-like definition of prime into a Java method. Write a `main()` method to test it.