Hi,
Does anyone know a method or some code to find out whether two numbers have at least one common factor?
I currently have a gcd method that finds the greatest common divisor between two numbers however an arithmetic exception is thrown if the two numbers have no common divisor. The problem is i do not want this exception thrown so i need to check there is at least one factor between the numbers before i call the gcd method on them.
Any help would be appreciated,
Thanks
> i need to check there is at least one factor between the numbers before i call the gcd method on them.
No. You need to fix the gcd code. Hint: any two numbers have a common factor 1.
I've tried writing a function to check whether there are more common factors than just 1 but it doesn't give the right result.
This is my code:
public boolean commonFactors(int p, int q){
int count = 0;
if(p>q){
for(int i = q;i< p;i++){
if((q%i==0)&&(p%i==0)){
count++;
}
}
}
else if(q>p){
for(int i = p;i< q;i++){
if((p%i==0)&&(q%i==0)){
count++;
}
}
}
else{
count = 2;
}
if(count>1){
return true;
}
else{
return false;
}
}Can anyone see why it is not working?
Thanks
From what i can see, in cases where there is only one other common factor than 1, your method will return false, because 1 isn't accounted for in your count.
Count should either start at 1 (because we know all pairs have 1) or you should change your condition so that it knows we're ignoring 1 as a common factor. :)
Tried changing count to 1 but still no luck.
This method is for any integers by the way (Integer.MIN_VALUE to Integer.MAX_VALUE).
Can anyone help?
Hang on, common factor, as in, 2 is a common factor of 4 and 6?
It's probably because you always start your for loop at the value of the smaller of your pair, so the only common factor it will pick up is one in the range between the two.
You probably want to start the forloop at 2, so it can check all of the lower numbers.
Altered my method to this now and it seems to work for positive numbers:
public boolean commonFactors(int p, int q){
int count = 0;
if(q > p){
for(int i = 1;i < q;i++){
if((q%i==0)&&(p%i==0)){
count++;
}
}
}
else if(p > q){
for(int i = 1;i < p;i++){
if((p%i==0)&&(q%i==0)){
count++;
}
}
}
else{
count = 2;
}
if(count>1){
return true;
}
else{
return false;
}
}I'm guessing to make it work for negative numbers and a mix of a positive and negative numbers also, i'll have to turn the negative numbers into positive representations (e.g. -2 to 2) first?
Only problem with that will be that turning Integer.MIN_VALUE into a positive number results in an unrepresentable number so in this case i will have to divide Integer.MIN_VALUE by 2 first before making it positive?
Is this a reasonable theory/solution do you think?
Thanks for all of your help by the way.
Yes, just using the absolute value is a good idea, and you will indeed have that problem. Seems like a good solution to me, considering this is the only case where you could have a problem of that nature, good stuff :)
no problem! :)
Hi,
Does anyone know a method or some code to find out whether two numbers have at least one common factor?
I currently have a gcd method that finds the greatest common divisor between two numbers however an arithmetic exception is thrown if the two numbers have no common divisor. The problem is i do not want this exception thrown so i need to check there is at least one factor between the numbers before i call the gcd method on them.
Any help would be appreciated,
Thanks
Alright. First off. Can u show your GCD method? And is your primary objective is to find the gcd or factors only?
These are both of the important methods. The problem was that gcd threw an arithmetic exception if there were no common factors (e.g. if q did not reach 0) so i've been trying to create a method (commonFactors) that shows if two integers (between and including MIN and MAX values) have common factors so i can use it to prevent the gcd error first. Still in the process of making commonFactors work for negative numbers as stated in my last post.
public static int gcd(int p, int q){
if (q == 0)
return p;
return gcd(q, p % q);
}
public boolean commonFactors(int p, int q){
int count = 0;
if(q > p){
for(int i = 1;i < q;i++){
if((q%i==0)&&(p%i==0)){
count++;
}
}
}
else if(p > q){
for(int i = 1;i < p;i++){
if((p%i==0)&&(q%i==0)){
count++;
}
}
}
else{
count = 2;
}
if(count>1){
return true;
}
else{
return false;
}
}Your GCD code is working perfectly for me. If there are not common factors the p and q parameters become "1" and thus in next call q would become 0. hence 1 will be returned.
Post your entire code...the place where you are using this method. if possible post the exception stack trace also.
I've created a small test program to print gcds:
package fractions;
public class TestFraction {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Fraction f = new Fraction(Integer.MIN_VALUE, Integer.MAX_VALUE);
int result = f.getGCD();
System.out.println(result);
}
}The error i am getting when i run it is:
Exception in thread "main" java.lang.ArithmeticException
at fractions.Fraction.<init>(Fraction.java:66)
at fractions.TestFraction.main(TestFraction.java:10)My Fraction constructor (with the line where the exception is apparently thrown from in bold) is:
public Fraction(int n, int d) throws ArithmeticException{
int gcd1 = gcd(n, d);
n = n/gcd1;
d = d/gcd1;
if(d<0){
if(n==Integer.MIN_VALUE){
[B]throw new ArithmeticException();[/B]
}
else{
n = n*-1;
d = d*-1;
}
}
else if(d==0){
throw new ArithmeticException();
}
else if(n==0){
d = 1;
}
this.numerator = n;
this.denominator = d;
}I am not sure how that exception is thrown as:
- I think the gcd of Integer.MIN_VALUE and Integer.MAX_VALUE is 1? or is it -1?
- So if it is, the denominator should stay as Integer.MAX_VALUE, so i don't know why it is passing through the d<0 condition?
anyone?
???
Well I cant figure out what you are trying to do in the constructor. Please state what it must do.
And the GCD between the min and max values is 1. There is no such thing as a negative gcd. so use only absolute values.
public Fraction(int n, int d) throws ArithmeticException{
//Calculates gcd between the num and den integers
int gcd1 = gcd(n, d);
//Simplifies the fraction using the gcd e.g. 10/20 becomes 1/2
n = n/gcd1;
d = d/gcd1;
/** Checks if the denominator is negative; if it is, it must be converted
* to positive and the num be made negative (e.g. 1/-2 becomes -1/2)
if(d<0){
/** If the den is negative and the num is Integer.MIN_VALUE, obviously
* the num cannot be made positive as in this case it would be
* unrepresentable thus the exception is thrown first */
if(n==Integer.MIN_VALUE){
[B]throw new ArithmeticException();[/B]
}
//Otherwise the negativity/positivity of the integers are changed
//accordingly
else{
n = n*-1;
d = d*-1;
}
}
//If the denominator is 0 an exception is thrown
else if(d==0){
throw new ArithmeticException();
}
//If the numerator is 0 the denominator becomes 1
else if(n==0){
d = 1;
}
//The fraction is constructed
this.numerator = n;
this.denominator = d;
}I have highlighted in bold the line where the test program reaches but i do not understand why it gets there as stated in my last code post.
Thanks for the help
Well isnt it obvious why the control reaches that point?
The gcd is 1 for Integer.MIN_VALUE and Integer.MAX_VALUE.
So the numerator is the MIN_VALUE and thats why u get the exception.
n = n/gcd1;
d = d/gcd1;
/** Checks if the denominator is negative; if it is, it must be converted
* to positive and the num be made negative (e.g. 1/-2 becomes -1/2)
[B]if(d<0)[/B]{
/** If the den is negative and the num is Integer.MIN_VALUE, obviously
* the num cannot be made positive as in this case it would be
* unrepresentable thus the exception is thrown first */
if(n==Integer.MIN_VALUE){
throw new ArithmeticException();
}
//Otherwise the negativity/positivity of the integers are changed
//accordingly
else{
n = n*-1;
d = d*-1;
}
}It should not get to that condition though to check if the num is MIN_VALUE?
For instance,
If the gcd is 1,
d = d/gcd1 (MAX_VALUE/1) which keeps d as MAX_VALUE still,
so how does d pass through the condition in bold (d<0) if it is still MAX_VALUE?
Use absolute values to calculate GCD. Acc to your code gcd is -1 so when you divide the denominator it becomes negative. So make your gcd positive or use absolute values when calculating gcd.
I can't use an absolute value for Integer.MIN_VALUE though as that is unrepresentable?
So is it better to just insert an if statement within the fraction constructor to turn the gcd into its absolute value after the gcd is calculated?
Thanks
Yeah youre right. You just change your gcd to positive and everything should work fine.
Added the if statement and the 7 JUnitTests i had all passed so looks as though it works!
Going to add more of the tests and see if the all pass.
Thanks for all of your help, much appreciated :)
Welcome.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.