Learning Objectives Implementing a Menu-Driven Application Modular Programming In class we discussed how functions can be used to do modular programming. Rather than write a program that consists of only the main function, we can disaggregate the overall task of a program into more manageable subtasks. The maintenance, implementation and design of a program becomes easier. We can then write functions to solve the subtasks making up the program. In this project, you will write a menu-driven application that performs various tasks involving elementary numerical algorithms. Subtasks in the program will be carried out by functions. For now, all the functions will be defined in the same file, NumericalAlgorithmsDemo.cpp, as the main function. We discuss the functions and the associated algorithms below: The Text-Based Menu Interface

/**

* Displays the text-based menu interface for the program:

* B A S I C N U M E R I C A L A L G O R I T H M S M E N U

* -------------------------------------------------------------

* [1] Greatest Common Divisor and Least Common Factors

* [2] Greatest Prime Factor

* [3] Relative Prime Test

* [4] Prime Test

* [0] Quit

* ------------------------------------------------------------

*/ void menu() Greatest Common Divisor and Least Common Multiple

Definition 1. The greatest common divisor, sometimes also called the highest common divisor, of two positive integers a and b is the largest divisor common to a and b. For example, GCD(3, 5) = 1, GCD(12, 60) = 12, and GCD(12, 90) = 6. Duncan 1 Fall 2018 COPYRIGHT Numerical Algorithms CSc 1253: Programming Project # 3 In order to find the GCD of two integers, n1 and n2, these steps are followed: 1. Take the absolute value of both numbers to ensure that they are both non-negative: let a = |n1| and b = |n2|. 2. If both a and b are 0, the GCD is undefined. 3. If neither number is 0, repeat these steps until b is 0. (a) temp = a mod b (b) a = b (c) b = temp The value of a when b is 0, is GCD(n1, n2). These steps describe the Euclidean GCD algorithm.

Definition 2. The least common multiple of two numbers a and b, variously denoted LCM(a, b) is the smallest positive number m that both a and b can divide. For example, LCM(3, 5) = 15, LCM(12, 60) = 60, and LCM(12, 90) = 180. The LCM is undefined when either number is 0. The equivalence between LCM and GCD is as follows: LCM(a, b) = a GCD(a, b) b (1) Implement the function below:

/** * Computes the GCD and LCM of the specified numbers. The lCM is

* set to 0 if either n1 or n2 is 0 and gCD is set to 0 if both

* n1 and n2 are 0 as an indication that they are undefined.

* @param n1 an integer

* @param n2 an integer

* @param lCM the least common multiple

* @param gCD the greatest common denominator

*/ void gCDLCM(int n1, int n2, int &lCM, int &gCD)

Definition 3. Two nonzero integers are said to be relatively prime if they have no common positive factor except 1; that is, if their GCD is 1. If either number is 0, then the numbers are not relatively prime. For example, 15 and 8 are relatively prime but 25 and 20 are not relatively prime.

Implement the function below:

/**

* Determines whether the specified numbers are relatively prime

* @param n1 an integer

* @param n2 an integer

* @return true when the specified numbers are relatively prime;

* otherwise, false

*/ bool areRelPrimes(int n1, int n2)

A Primality Test

Definition 4. A prime number is any integer greater than 1 whose only factors are 1 and the number itself. Non-prime numbers are called composite numbers. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . The number 30 is not a prime number since 2, a number other than 1 and 30, can divide 30. Here are a series of rules that can be used to determine whether any integer less than 263 is a prime number. 1. A number less than 2 is a composite number. 2. 2, 3 or 5 are the only prime numbers less than 7. 3. Even numbers other than 2 are not prime numbers. 4. An integer greater than 6 that is not of the form 6k+1 or 6k+5, where k is a positive integer, is a composite number. 5. For any other integer, if it is divisible by an integer in the range 3, 5, 7 n, then it is a composite number; otherwise, it is a prime number. Implement the function below:

/**

* Determines whether or not an integer <= 2^63 is prime

* @param n an integer

* @return true when the number is prime; otherwise, false

*/ bool isPrime(int n)

Greatest Prime Factor

Definition 5. The greatest prime factor, denoted gpf, of an integer greater than or equal to 2 is the largest prime number that can evenly divide the number. These steps may be used to determine the gpf of a number. 1. The greatest prime factor is undefined for an integer less than 2. 2. For integers greater than or equals to 2, try integers in the range 2, , n to determine the largest prime number that divides the n. Repeat these steps as long as n is greater than k for values k = 2, , n. (a) As long as k divides n, update n as follows: n = number k (b) Try the next value of k. The last value of n is the greatest prime factor of the number.

/**

* Computes the greatest prime factor of the specified integer

* @param n an integer

* @return the gpf of the specified number or 0 when the

* specified number is less than 2.

*/ int gPF(int n)

The Main Function

When your program begins to run, it displays a menu by calling the menu function. It then prompts the user to select an option. If the user does not select a valid option, an error message is displayed and then the menu is displayed again. When the user selects menu option 1, the user is prompted to enter two integers. The gCDLCM function is then called to compute the GCD and LCM of the numbers. Suppose m and n are the users inputs. If the calculated GCD is 0, your program prints GCD(m,n) = NaN . If the calculated GCD is a non-zero number, NaN is replaced with the calculated value. If the calculated LCM is 0, your program prints LCM(m,n) = NaN . If the calculated LCM is a non-zero number, NaN is replaced with the calculated value.