GREATEST_COMMON_DIVISOR
The C++ program featured in this tutorial web page computes the greatest common divisor of two natural numbers, A and B, using the Euclidean algorithm to iteratively (i.e. in a step-by-step manner) divide A by B in order to obtain the nonnegative integer remainder of that division and then (in the next step (if there is a next step)) set A to B and B to that remainder before dividing A by B in order to obtain the nonnegative integer of that division (and continuing that process until a remainder of zero is obtained). When a remainder of zero is obtained, the least common denominator of the original A and B values is the latest value of B.
To view hidden text inside each of the preformatted text boxes below, scroll horizontally.
// Pseudocode describing how the Euclidean algorithm is used to compute the greatest common divisor of positive integers A and B. PROCEDURE gcd(A,B): WHILE B IS NOT EQUAL TO ZERO: LET remainder be the result of the computation A mod B. LET A be B. LET B be remainder. END WHILE RETURN B. END PROCEDURE
SOFTWARE_APPLICATION_COMPONENTS
C++_source_file: https://raw.githubusercontent.com/karlinarayberinger/KARLINA_OBJECT_extension_pack_21/main/greatest_common_divisor.cpp
plain-text_file: https://raw.githubusercontent.com/karlinarayberinger/KARLINA_OBJECT_extension_pack_21/main/greatest_common_divisor_output.txt
PROGRAM_COMPILATION_AND_EXECUTION
STEP_0: Copy and paste the C++ source code into a new text editor document and save that document as the following file name:
greatest_common_divisor.cpp
STEP_1: Open a Unix command line terminal application and set the current directory to wherever the C++ program file is located on the local machine (e.g. Desktop).
cd Desktop
STEP_2: Compile the C++ file into machine-executable instructions (i.e. object file) and then into an executable piece of software named app using the following command:
g++ greatest_common_divisor.cpp -o app
STEP_3: If the program compilation command does not work, then use the following commands (in top-down order) to install the C/C++ compiler (which is part of the GNU Compiler Collection (GCC)):
sudo apt install build-essential
sudo apt-get install g++
STEP_4: After running the g++ command, run the executable file using the following command:
./app
STEP_5: Once the application is running, the following prompt will appear:
Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000:
STEP_6: Enter a value for A using the keyboard.
(Proceed from there inputting B and other program values in accordance to the prompt messages).
STEP_7: Observe program results on the command line terminal and in the output file.
PROGRAM_SOURCE_CODE
The text in the preformatted text box below appears on this web page (while rendered correctly by the web browser) to be identical to the content of the C++ source code file whose Uniform Resource Locator is displayed in the green hyperlink below. A computer interprets that C++ source code as a series of programmatic instructions (i.e. software) which govern how the hardware of that computer behaves.
(Note that angle brackets which resemble HTML tags (i.e. an “is less than” symbol (i.e. ‘<‘) followed by an “is greater than” symbol (i.e. ‘>’)) displayed on this web page have been replaced (at the source code level of this web page) with the Unicode symbols U+003C (which is rendered by the web browser as ‘<‘) and U+003E (which is rendered by the web browser as ‘>’). That is because the WordPress web page editor or web browser interprets a plain-text version of an “is less than” symbol followed by an “is greater than” symbol as being an opening HTML tag (which means that the WordPress web page editor or web browser deletes or fails to display those (plain-text) inequality symbols and the content between those (plain-text) inequality symbols)).
C++_source_file: https://raw.githubusercontent.com/karlinarayberinger/KARLINA_OBJECT_extension_pack_21/main/greatest_common_divisor.cpp
/**
* file: greatest_common_divisor.cpp
* type: C++ (source file)
* date: 26_SEPTEMBER_2024
* author: karbytes
* license: PUBLIC_DOMAIN
*/
/** preprocessing directives */
#include <iostream> // standard input (std::cin), standard output (std::cout)
#include <fstream> // output file creation, output file overwriting, output file open, output file close
#define MAXIMUM_INPUT_VALUE 10000 // constant which represents the maximum value for A and for B
/** function prototype */
void print_greatest_common_divisor_computation_steps(int A, int B, std::ostream& output);
/** program entry point */
int main()
{
// Declare and initialize three int type variables.
int A = 1, B = 1, input_additional_values = 1;
// Declare a file output stream handler.
std::ofstream file;
/**
* If the file named greatest_common_divisor.txt does not already exist
* inside of the same file directory as the file named greatest_common_divisor.cpp,
* create a new file named greatest_common_divisor_output.txt in that directory.
*
* Open the plain-text file named greatest_common_divisor_output.txt
* and set that file to be overwritten with program data.
*/
file.open("greatest_common_divisor_output.txt");
// Print an opening message to the command line terminal.
std::cout << "\n\n--------------------------------";
std::cout << "\nStart Of Program";
std::cout << "\n--------------------------------";
// Print an opening message to the file output stream.
file << "--------------------------------";
file << "\nStart Of Program";
file << "\n--------------------------------";
// Print "This C++ program computes the greatest common divisor of two natural numbers and prints the steps involved." to the command line terminal and to the file output stream.
std::cout << "\n\nThis C++ program computes the greatest common divisor of two natural numbers and prints the steps involved.";
file << "\n\nThis C++ program computes the greatest common divisor of two natural numbers and prints the steps involved.";
while (input_additional_values != 0)
{
// Print a horizontal divider line to the command line terminal and to the file output stream.
std::cout << "\n\n--------------------------------";
file << "\n\n--------------------------------";
// Prompt the user to enter an input value for A (and print that prompt to the command line terminal and to the file output stream).
std::cout << "\n\nEnter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than " << MAXIMUM_INPUT_VALUE << ": ";
file << "\n\nEnter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than " << MAXIMUM_INPUT_VALUE << ": ";
// Scan the command line terminal for the most recent keyboard input value. Store that value in A.
std::cin >> A;
// Print "The value which was entered for A is {A}." to the command line terminal and to the file output stream.
std::cout << "\nThe value which was entered for A is " << A << ".";
file << "\n\nThe value which was entered for A is " << A << ".";
/**
* If A is smaller than 1 or if A is larger than MAXIMUM_INPUT_VALUE, set A to 1.
*
* Print "A has been reset to 1 due to the fact that the input value for A was either less than one or else greater than {MAXIMUM_INPUT_VALUE}."
* to the command line terminal and to the file output stream.
*/
if ((A < 1) || (A > MAXIMUM_INPUT_VALUE))
{
A = 1;
std::cout << "\n\nA has been reset to 1 due to the fact that the input value for A was either less than one or else greater than " << MAXIMUM_INPUT_VALUE << ".";
file << "\n\nA has been reset to 1 due to the fact that the input value for A was either less than one or else greater than " << MAXIMUM_INPUT_VALUE << ".";
}
// Print a horizontal divider line to the command line terminal and to the file output stream.
std::cout << "\n\n--------------------------------";
file << "\n\n--------------------------------";
// Prompt the user to enter an input value for B (and print that prompt to the command line terminal and to the file output stream).
std::cout << "\n\nEnter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than " << MAXIMUM_INPUT_VALUE << ": ";
file << "\n\nEnter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than " << MAXIMUM_INPUT_VALUE << ": ";
// Scan the command line terminal for the most recent keyboard input value. Store that value in B.
std::cin >> B;
// Print "The value which was entered for B is {B}." to the command line terminal and to the file output stream.
std::cout << "\nThe value which was entered for B is " << B << ".";
file << "\n\nThe value which was entered for B is " << B << ".";
/**
* If B is smaller than 1 or if B is larger than MAXIMUM_INPUT_VALUE, set B to 1.
*
* Print "B has been reset to 1 due to the fact that the input value for B was either less than one or else greater than {MAXIMUM_INPUT_VALUE}."
* to the command line terminal and to the file output stream.
*/
if ((B < 1) || (B > MAXIMUM_INPUT_VALUE))
{
B = 1;
std::cout << "\n\nB has been reset to 1 due to the fact that the input value for B was either less than one or else greater than " << MAXIMUM_INPUT_VALUE << ".";
file << "\n\nB has been reset to 1 due to the fact that the input value for B was either less than one or else greater than " << MAXIMUM_INPUT_VALUE << ".";
}
// Print a horizontal divider line to the command line terminal and to the file output stream.
std::cout << "\n\n--------------------------------";
file << "\n\n--------------------------------";
// Execute the greatest common divisor function (defined by this C++ source file) such that the computation steps and final result are printed to the comand line terminal.
print_greatest_common_divisor_computation_steps(A, B, std::cout);
// Execute the greatest common divisor function (defined by this C++ source file) such that the computation steps and final result are printed to the file output stream.
print_greatest_common_divisor_computation_steps(A, B, file);
// Ask the user whether or not to continue inputing values.
std::cout << "\n\nWould you like to input new values for A and B? (Enter 1 if YES. Enter 0 if NO): ";
// Scan the command line terminal for the most recent keyboard input value.
std::cin >> input_additional_values;
}
// Print a closing message to the command line terminal.
std::cout << "\n\n--------------------------------";
std::cout << "\nEnd Of Program";
std::cout << "\n--------------------------------\n\n";
// Print a closing message to the file output stream.
file << "\n\n--------------------------------";
file << "\nEnd Of Program";
file << "\n--------------------------------";
// Close the file output stream.
file.close();
// Exit the program.
return 0;
}
/**
* Use the Euclidean algorithm to compute the greatest common divisor of positive integers A and B.
*
* (This function assumes that A and B are each natural numbers which are not too large to be overflow values (i.e. values which are too large to be properly represented as positive quantities in the C++ int type variable)).
*
* (This function assumes that output is either std::cout, some ofstream object (pointing to a valid output file), or some other valid C++ output stream object).
*
* Print each step of that iterative process to the output stream.
*/
void print_greatest_common_divisor_computation_steps(int A, int B, std::ostream& output)
{
int i = 0, remainder = 0;
output << "\n\nComputing the greatest common divisor of A and B using the Euclidean algorithm...";
while (B != 0)
{
remainder = A % B;
output << "\n\nstep_" << i << ": ";
output << "A = " << A << ", B = " << B << ", gcd(A,B) = A % B = " << remainder << ".";
A = B;
B = remainder;
i += 1;
}
output << "\n\nThe greatest common divisor of A and B is " << A;
}
SAMPLE_PROGRAM_OUTPUT
The text in the preformatted text box below was generated by one use case of the C++ program featured in this computer programming tutorial web page.
plain-text_file: https://raw.githubusercontent.com/karlinarayberinger/KARLINA_OBJECT_extension_pack_21/main/greatest_common_divisor_output.txt
-------------------------------- Start Of Program -------------------------------- This C++ program computes the greatest common divisor of two natural numbers and prints the steps involved. -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 10. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 9. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 10, B = 9, gcd(A,B) = A % B = 1. step_1: A = 9, B = 1, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 1 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 10. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 20. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 10, B = 20, gcd(A,B) = A % B = 10. step_1: A = 20, B = 10, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 10 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 144. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 99. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 144, B = 99, gcd(A,B) = A % B = 45. step_1: A = 99, B = 45, gcd(A,B) = A % B = 9. step_2: A = 45, B = 9, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 9 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is -11. A has been reset to 1 due to the fact that the input value for A was either less than one or else greater than 10000. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is -11. B has been reset to 1 due to the fact that the input value for B was either less than one or else greater than 10000. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 1, B = 1, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 1 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 10001. A has been reset to 1 due to the fact that the input value for A was either less than one or else greater than 10000. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 10001. B has been reset to 1 due to the fact that the input value for B was either less than one or else greater than 10000. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 1, B = 1, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 1 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 10000. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 10000. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 10000, B = 10000, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 10000 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 0. A has been reset to 1 due to the fact that the input value for A was either less than one or else greater than 10000. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 0. B has been reset to 1 due to the fact that the input value for B was either less than one or else greater than 10000. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 1, B = 1, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 1 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 1. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 1. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 1, B = 1, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 1 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 666. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 303. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 666, B = 303, gcd(A,B) = A % B = 60. step_1: A = 303, B = 60, gcd(A,B) = A % B = 3. step_2: A = 60, B = 3, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 3 -------------------------------- Enter the first of two natural numbers (which will be stored in an int type variable named A) which is no larger than 10000: The value which was entered for A is 1024. -------------------------------- Enter the second of two natural numbers (which will be stored in an int type variable named B) which is no larger than 10000: The value which was entered for B is 888. -------------------------------- Computing the greatest common divisor of A and B using the Euclidean algorithm... step_0: A = 1024, B = 888, gcd(A,B) = A % B = 136. step_1: A = 888, B = 136, gcd(A,B) = A % B = 72. step_2: A = 136, B = 72, gcd(A,B) = A % B = 64. step_3: A = 72, B = 64, gcd(A,B) = A % B = 8. step_4: A = 64, B = 8, gcd(A,B) = A % B = 0. The greatest common divisor of A and B is 8 -------------------------------- End Of Program --------------------------------
This web page was last updated on 17_OCTOBER_2024. The content displayed on this web page is licensed as PUBLIC_DOMAIN intellectual property.