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 by coolfriends: n/a

3
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by ssharish2005

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 by nezachem: n/a