Programming in C

104 Chapter 7 Working with Arrays

34

55

89

144

233

377

The first two Fibonacci numbers, called F 0 and F 1 ,are defined to be 0 and 1 ,respective-

ly.Thereafter, each successive Fibonacci number Fiis defined to be the sum of the two

preceding Fibonacci numbers Fi– 2 and Fi– 1. So F 2 is calculated by adding together the

values of F 0 and F 1. In the preceding program, this corresponds directly to calculating

Fibonacci[2]by adding the values Fibonacci[0]and Fibonacci[1].This calculation

is performed inside the forloop, which calculates the values of F 2 through F 14 (or,

equivalently,Fibonacci[2]through Fibonacci[14]).

Fibonacci numbers actually have many applications in the field of mathematics and in

the study of computer algorithms.The sequence of Fibonacci numbers historically origi-

nated from the “rabbits problem”: If you start with a pair of rabbits and assume that each

pair of rabbits produces a new pair of rabbits each month, that each newly born pair of

rabbits can produce offspring by the end of their second month, and that rabbits never

die, how many pairs of rabbits will you have after the end of one year? The answer to

this problem rests in the fact that at the end of the nth month, there will be a total of

Fn+ 2 rabbits.Therefore, according to the table from Program 7.3, at the end of the

twelfth month, you will have a total of 377 pairs of rabbits.

Using an Array to Generate Prime Numbers

Now, it’s time to return to the prime number program that you developed in Chapter 6,

“Making Decisions,” and see how the use of an array can help you to develop a more

efficient program. In Program 6.10A, the criteria that you used for determining if a

number was prime was to divide the prime candidate by all successive integers from 2

up to the number –1. In exercise 7 in Chapter 6, you noted two inefficiencies with this

approach that could easily be corrected. But even with these changes, the approach used

is still not efficient. Although such questions of efficiency might not be important when

dealing with a table of prime numbers up to 50, these questions do become important,

for example, when you start thinking about generating a table of prime numbers up to

1,000,000.

An improved method for generating prime numbers involves the notion that a num-

ber is prime if it is not evenly divisible by any other prime number.This stems from the

fact that any nonprime integer can be expressed as a multiple of prime factors. (For

example, 20 has the prime factors 2, 2, and 5.) You can use this added insight to develop

a more efficient prime number program.The program can test if a given integer is prime

by determining if it is evenly divisible by any other previously generated prime. By now

Program 7.3 Continued