Program to display the greatest common divisor , C/C++ Programming

Assignment Help:

Many modern cryptography algorithms require two numbers that are coprime, or sometimes referred to as relatively prime. Two numbers are coprime if their greatest common divisor is 1. A Greek mathematician named Euclid, who lived about 300 B.C. and who is known as the father of Geometry, created a very efficient algorithm for finding the greatest common divisor (gcd) of two positive integers. The gcd of two positive integers is defined as the greatest positive integer that divides both numbers without a remainder (has a remainder of zero).

Method using subtraction: Step 1 - Subtract the lesser value from the greater value. If the difference is equal to the lesser value, then the gcd is found and it is equal to the lesser value. Otherwise, if the difference is greater than the lesser value then the difference becomes the greater value, and repeat step 1. If the difference is less than the lesser value, then the lesser value becomes the greater value and the difference becomes the lesser value. Then repeat step 1. Let's do an example with 84 and 18.

gcd(84, 18) = gcd(84 - 18, 18) = gcd(66, 18)

gcd(66, 18) = gcd(66 - 18, 18) = gcd(48, 18)

gcd(48, 18) = gcd(48 - 18, 18) = gcd(30, 18)

gcd(30, 18) = gcd(30 - 18, 18) = gcd(12, 18) switch greater and lesser.

gcd(18, 12) = gcd(18 - 12, 12) = gcd(6, 12) switch again.

gcd(12, 6 = gcd(12 - 6, 6) = gcd(6, 6)

Therefore gcd(84, 18) = 6.

Assignment:

Write a C++ program to calculate and display the greatest common divisor of two positive integers. If the greatest common divisor is 1, then announce that the two integers are coprime.

Design Considerations:

Part of this assignment is to get used to programming with functions, so you are required to use the following functions, or something quite similar:

void swapIfNecessary(long & greater, long & lesser);

// Notice this function uses reference parameters. If lesser > greater,

// then swap the values. Otherwise do not swap the values.

long gcd(long val1, long val2);

// This function returns the greatest common divisor of val1 and val2. Basically, after you ask the user for the values, you will call this function from the main function and it will do all the work.

Sample output 1:

Welcome to the gcd calculator. This program will calculate the

greatest common divisor of two positive integers.

Please enter the first positive integer : 93

Please enter the second positive integer : 51

The gcd of 93 and 51 is 3.

The numbers are not coprime.

Sample output 2:

Welcome to the gcd calculator. This program will calculate the

greatest common divisor of two positive integers.

Please enter the first positive integer : 51

Please enter the second positive integer : 62

The gcd of 51 and 62 is 1.

The numbers are coprime.

Deliverables:

Please name your file a05.cpp.  Upload your program source code (a05.cpp file) as usual.  Be sure to comment your code as required, and to acknowledge any sources of help you may have received.  Your header comments should include the identification of the assignment and your name.  It should also include a comment indicating any sources of help you may have received. If there were none, the line should read:

// Sources: None.

Points will be awarded for the following attributes of your solution:

a.   If your program does not compile, you get only 3 points irrespective of what the error is.

b.   If  it compiles, I check and deduct points for the following:

i.    Your file name must be a05.cpp

ii.   Your header section must have "Sources:" line to include any sources you may have used.

iii.  The quality of your source code (Form).  In particular, pay attention to your indentation, capitalization, and so forth.  Be sure to read the class C++ style guide before working on this problem. However, if you follow the style used in the book you will be fine!

iv.  Your program must use functions.

c.   Program works as specified, and does not have the above mentioned deficits, full points will be awarded.


Related Discussions:- Program to display the greatest common divisor

Object oriented programming and cryptography, This assignment document will...

This assignment document will be distributed from Blackboard assignment folder. Some parts of the assignments will require you to research answers from your text book (you must rea

Area under curve, Write a program to find the area under the curve y = f(x)...

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b.

What is an explicit constructor, A conversion constructor declared with the...

A conversion constructor declared with the explicit keyword. The compiler does not use an explicit constructor to execute an implied conversion of types. Its purpose is reserved ex

FILES, My file pointer is going to the location which i specified and writi...

My file pointer is going to the location which i specified and writing the value but it is in next line so,please help me iam developing in visual studio6

Area, Write a program to find the area under the curve y = f(x) between x =...

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

Big M method, I Want a answer for solving the big M method in the topic of ...

I Want a answer for solving the big M method in the topic of simplex method...

Copy constructor and an overloaded assignment operator, What is the differe...

What is the difference among a copy constructor and an overloaded assignment operator? Ans) A copy constructor constructs a latest object by using the content of the argument

Described c++ storage classes?, A: auto: the default. Variables are created...

A: auto: the default. Variables are created and initialized automatically while they are defined and destroyed at the ending of the block containing their definition. They are not

Android - iphone mobile game, I am seeking a developer to create a mobile g...

I am seeking a developer to create a mobile game for me. I want an endless runner game with simple controls. The game needs to be a 3D game in a 2D view. The graphics and animation

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd