Hey all… I’m stumped on a C++ program I have to create that involves simplifying radicals. It has to be able to take in a number, say the square root of 45 (the user just enters 45), and simplify it to 3 square roots of 5… I had a few ideas which haven’t worked out, so does any master C++ programmers out there have any ideas?
If this is your homework, you must be in college at least…
Basically, you’re being asked to break down a number into several smaller numbers that, when multiplied together, will produce it. To do this “right” (I guess?), the smaller numbers should be primes so a square root won’t simplify them any more.
An overview of the process of prime factorization can be found on this most excellent page (goddamn is Stephen Wolfram ever smart…):
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
In your case, I wouldn’t bother with any of the complicated algorithms. Just do the simplest one, “trial division”. Basically, divide the number entered by all primes smaller than sqrt(the number entered), and see which ones divide it evenly without any remainder. These are your prime factors. Now, sometimes there are multiple, uh… copies of a prime factor in a number. For instance, the prime factors of 12 are 2 and 3. However, 2 * 3 != 12. It’s 2 * 2 * 3 == 12. So be careful.
As you’re probably aware, in C++ the “%” (modulo/remainder) operator performs the “divides evenly without remainder” operation. If (x % y == 0), then x is evenly divisible by y with no remainder.
So you know what to do now, and you probably have a vague idea how to set up a loop to do it. The only thing left is to generate the list of primes less than sqrt(the number entered). For that I suggest the simplest possible way also, which is probably some kind of Sieve of Erastosthenes kinda deal.
Basically, make a list of all the integers from 2 to sqrt(the number entered). Then starting at 3, try and divide the current number in the in list by all of the numbers before it. If the current number is evenly divisible (there’s that % operator again) by any number before it on the list, then the current number is not prime. Strike it from the list. If the current number does not divide evenly by any of the numbers before it, it is by definition prime and you should leave it on the list. In either case, go on to the next number. After you’ve checked the last number on the list, you will have a list of all prime numbers less than sqrt(the number entered). Now you just have to figure out which ones are actually factors of the number.
This is turning out to be a fairly challenging program to get right! You have two fairly tricky loops to make. (find primes less than sqrt(n), find which are factors and how many of each factor) Good luck, you have a pretty decent coding and debugging ahead of you.
-Ben
This sounds like a homework problem to me…
Your problem isn’t clear to me. Is it that you haven’t figured out the algorithm to make the program work, or that you are having technical problems implementing the algorithm in C++?
If it’s the algorithm you’re having trouble with, try working out a few examples by hand and analyzing each step. I can’t think of any elegant way of doing what you describe off the top of my head, just ugly brute force/iterative methods. What you’re basically doing is factoring the number (e.g., 45) and figuring out which of the factors is the perfect square of another integer.
Eg. 45’s factors are
(45)
15
9
5
3
(1)
and the “brute force/dumb” way to find out what these factors are would be to do 45 MODULO 2, 45 MODULO 3… 45 MODULO (45/2). If 45 MODULO x == 0, then x is a factor.
Once you have all the factors (the x’s), you need to figure out if at least one x is a perfect square (4, 9, 16, 25 etc.) If there is one such x then you can reduce the radical, if there is no such x you cannot.
I know that’s not everything you need to write the program and solve the problem but hopefully it will give you some ideas.
On preview I see Mike has also made a suggestion, but it’s not like that has ever stopped anyone from posting anyway.
Here is the solution:
#include <math.h>
#include <iostream.h>
void main(){
int x = 0;
cout << "input radical to be simplified:";
cin >> x;
for (int y = floor(sqrt(x)); y > 0; y--) {
if (y == 1) {
cout << "sqrt(" << x << ") - no simplification" << endl;
break;
}
if (x%(y*y) == 0) {
if (x/(y*y) == 1) {
cout << y << endl;
break;
} else {
cout << y << " * sqrt(" << (x/(y*y)) << ")" << endl;
break;
}
}
}
}
Basically, start a downward counting loop, with the first number being the root of the largest square that is smaller than the number inputted. If that number (the square, not the root) divides evenly, then you can pull it out from under the radical.
I haven’t checked for valid inputs or if the algorithm is 100% complete (but I think it is).
And yes, I suppose you can start the loop at floor(sqrt(x/2)) instead, to save some iterations, but then you have to check for the case where x is a perfect square.
#include <math.h>
#include <iostream.h>
void main(){
int x = 0;
cout << "input radical to be simplified:";
cin >> x;
int y = sqrt(x);
if ((x/(y*y) == 1) && (x%(y*y) == 0)) {
cout << y << endl;
return;
}
y = sqrt(x/2);
for (; y > 0; y--) {
if (y == 1) {
cout << "sqrt(" << x << ") - no simplification" << endl;
break;
}
if (x%(y*y) == 0) {
cout << y << " * sqrt(" << (x/(y*y)) << ")" << endl;
break;
}
}
return;
}
One last mistake to correct:
if ((x/(y*y) == 1) && (x%(y*y) == 0)) {
should be:
if (x == y*y) {
The original works, but that’s what happens when you cut and paste too much.