In C++ compute the prime factorization of two numbers, then find their GCD (grea
ID: 3593622 • Letter: I
Question
In C++ compute the prime factorization of two numbers, then find their GCD (greatest common divisor) and their LCM (least common multiple). These concepts are of the utmost important in Number Theory and applications! you will be writing three functions.
First compute the prime factors of a number in the function getFactors. As a quick summary, we will start at the number 2 and see how many times 2 divides n. Every time 2 divides n evenly, we add it to our list of factors. When 2 does not divide n anymore, we then start the same process but for 3, and then for 4, then for 5 , etc. Here is an example run through of the algorithm:
let n = 180; let factors = {} 180 % 2 = 0 factors = {2} and n = 90 90 % 2 = 0 factors = {2, 2} and n = 45 45 % 2 = 1 factors = {2, 2} and n = 45 45 % 3 = 0 factors = {2, 2, 3} and n = 15 15 % 3 = 0 factors = {2, 2, 3, 3} and n = 5 5 % 4 = 1 factors = {2, 2, 3, 3} and n = 5 5 % 5 = 0 factors = {2, 2, 3, 3, 5} and n = 1 factors of 180 = {2, 2, 3, 3, 5} Q.E.D
a. We start with an int c ounter, we can call it c and we initialize it to 2
i. we will use this as the temporary factor
b. set up a while loop while n is not equal to 1 e.g. while (n != 1) { // ... }
c. inside of the while loop from step b, we want to see if our temporary factor divides into n evenly, that is, we want to see if there is any remainder after dividing n by c. we also want to do this until c no long divides n… sounds like another while loop! e,g, while (n % c == 0) { // ... }
d. inside of the while loop from step c, we want to divide n by c and save the quotient in n. we also want to push_back c into our factors vector. this will conclude the while loop from step c.
e. back inside the while loop from step b, but after the one from steps c and d, we need to increment c by 1. e.g. ++c;
f. at this point you can compile the program with the command make and run it yourself with ./main.exe to test it out.
3. Now we need to implement the GCD and LCM routines. First GCD:
a. The GCD is the greatest common divisor of two numbers. What this means is that if we take the only the common divisors (i.e. the intersection) of the two factorizations and multiply together, we get the GCD. Here is an example: p = 100 = 2 * 2 * 5 * 5 q = 30 = 2 * 3 * 5 gcd = 2 * 5 = 10
b. C++ gives us a function called set_intersection which takes in two (sorted) sets of numbers and provides us with the intersection of those two sets. the way we call this function is a tad clunky though... we need to pass in the beginning and end of each factorization vector, along with a special construction of a new vector.
i. first, create a new vector of ints named intersection
ii. now we need to make the call to set_intersection, passing in the beginning and end of pFactors, then the beginning and end of qFactors, then the special construction I mentioned up above. e.g. set_intersection(begin(pFactors), end(pFactors), begin(qFactors), end(qFactors), back_inserter(intersection));
c. now that we have the intersection of the prime factors, we need to just multiply them all together! we could very easily use a for-loop, but we have yet another function to do this for us!
i. the function accumulate much like set_intersection takes in ranges to vector-like objects, accept we have to tell it how to accumulate the values. a typical accumulation using addition, but we need multiplication:
e.g. gcd = accumulate(begin(intersection), end(intersection), 1, multiplies());
we now need to write the function to compute the LCM. thankfully we have done all of the heavy lifting, and so the routine to compute the LCM is really simple! once we have the GCD of two numbers, we can find the LCM as follows
a. simply implement this little formula for the lcm function and that is it!
main.cpp
#include <algorithm> // set_intersection
#include <iostream>
#include <numeric> // accumulate
#include <vector>
using namespace std;
vector<int> getFactors(int n)
{
vector<int> factors = {1};
// TODO:
// put the code that computes the factors here!
return factors;
}
int gcd(int p, int q)
{
vector<int> pFactors = getFactors(p);
vector<int> qFactors = getFactors(q);
int gcd = 0;
// TODO:
// put the code that computes the GCD here!
return gcd;
}
int lcm(int p, int q)
{
int lcm = 0;
// TODO:
// put the code that computes the LCM here!
return lcm;
}
void printFactors(const vector<int> &factors)
{
cout << "< ";
for (auto factor : factors)
{
cout << factor << " ";
}
cout << ">" << endl;
}
int main()
{
int p = 0;
cout << "Enter a positive integer for p:" << endl;
cin >> p;
int q = 0;
cout << "Enter a positive integer for q:" << endl;
cin >> q;
if (p < 1 || q < 1)
{
cerr << "ERROR: both p and q need to be positive integers! Received: " << p << ", " << q << endl;
return 1;
}
vector<int> pFactors = getFactors(p);
vector<int> qFactors = getFactors(q);
printFactors(pFactors);
printFactors(qFactors);
cout << "GCD = " << gcd(p, q) << endl;
cout << "LCM = " << lcm(p, q) << endl;
}v
Explanation / Answer
main.cpp
#include <algorithm> // set_intersection
#include <iostream>
#include <numeric> // accumulate
#include <vector>
using namespace std;
vector<int> getFactors(int n)
{
vector<int> factors={1};
// TODO:
// put the code that computes the factors here!
int c = 2;
while (n != 1)
{
while(n%c == 0)
{
n = n/c;
factors.push_back(c);
}
++c;
}
return factors;
}
int gcd(int p, int q)
{
vector<int> pFactors = getFactors(p);
vector<int> qFactors = getFactors(q);
int gcd = 0;
// TODO:
// put the code that computes the GCD here!
vector<int> intersection;//step 1
set_intersection(begin(pFactors), end(pFactors), begin(qFactors), end(qFactors), back_inserter(intersection));//step 2
gcd = accumulate(begin(intersection), end(intersection), 1, multiplies<int>());//step 3
return gcd;
}
int lcm(int p, int q)
{
int lcm = 0;
// TODO:
// put the code that computes the LCM here!
lcm = (p*q)/gcd(p,q);
return lcm;
}
void printFactors(const vector<int> &factors)
{
cout << "< ";
for (auto factor : factors)
{
cout << factor << " ";
}
cout << ">" << endl;
}
int main()
{
int p = 0;
cout << "Enter a positive integer for p:" << endl;
cin >> p;
int q = 0;
cout << "Enter a positive integer for q:" << endl;
cin >> q;
if (p < 1 || q < 1)
{
cerr << "ERROR: both p and q need to be positive integers! Received: " << p << ", " << q << endl;
return 1;
}
vector<int> pFactors = getFactors(p);
vector<int> qFactors = getFactors(q);
printFactors(pFactors);
printFactors(qFactors);
cout << "GCD = " << gcd(p, q) << endl;
cout << "LCM = " << lcm(p, q) << endl;
}
OUTPUT