Hey everyone,

I am working on this integer decomposition problem that I cant figure out. I would really apperciate your help on this.

Here is the problem:

It is known that every integer n greater than 17 may be written as the sum of three distinct integers, each greater than one, that are pairwise relatively prime; that is, no pair of the three integers have a common prime factor. Stated another way, their greatest common divisor is 1. To illustrate this fact, write a program that reads values of n from successive input lines and for each n show a decomposition of n into the sum of three integers a, b, and c by outputting a line of the form:

n = a + b + c

Your program may output any pairwise relatively prime decomposition. Furthermore the order of a, b, and c does not matter. Read n from command line.

This is what I have so far:

int gcd( int i, int j ) ;
int decompose( int x ) ;
int i, j, k ;

#include <stdio.h>
#include <stdlib.h>

int main( int argc, char *argv[] ) {

  int n, a, b, c ;

  n = atoi( argv[1] ) ;

  decompose( n ) ;
  
  printf( "\nInteger decomposition of %d is %d + %d + %d\n\n", n, a, b, c ) ;

return 0 ;  

}

int gcd( int i, int j ) {

  int x, y ;

  if( i > j ) {
    x = i ;
    y = j ;
 }
  else {
    y = i ;
    x = j ;
  }

  if( x % y == 0 ) return y ;
  else
    return gcd( y, ( x % y ) ) ;
}

int decompose( int x ) {

  int i, j, k ;

  for( i = 1 ; i < x ; i++ ) {
    for( j = ( i + 1 ) ; j < x ; j++ ) {
      for( k = ( j + 1 ) ; k < x ; k++ ) {
        if( ( i + j + k ) == x ) printf( "%d %d %d", i, j, k ) ;
          if( ( gcd (i, j ) == 1 ) && ( gcd( j, k ) == 1 ) && ( gcd ( k, i ) == 1 ) ) ; 
      }
    }
  }

  return 0 ;

}

I would really appreciate if someone could show me what is wrong with this code. Thanks in advance.

Edited 7 Years Ago by coolfriends: n/a

Pay attention to lines 48 and 49.
At line 48 you print (i, j, k) as soon as they sum up to x, regardless of their relative primarity. Then at line 49 you test their primarity - and do nothing with the result.
You should print data only if the test at line 49 succeeds.

By the way, a loop at line 47, along with test at line 48 just waste processor cycles. The value of k is known right away. Do you see what I mean?

Edited 7 Years Ago by nezachem: n/a

Comments
Thanks a lot

thanks a lot...it is working now...i should have realized about printing on the wrong line..

And also this line is gonna print junk

printf( "\nInteger decomposition of %d is %d + %d + %d\n\n", n, a, b, c ) ;

You might to return those i,j,k values back to main to print them accordingly.
-ssharish

This article has been dead for over six months. Start a new discussion instead.