# Check for co-primes

Discussion in 'C' started by meghna, Mar 14, 2006.

1. ### meghnaNew Member

Joined:
Mar 14, 2006
Messages:
3
0
Trophy Points:
0
Write a 'C' Program to Read two numbers and check whether they are Co-Primes or not

2. ### coderzoneSuper Moderator

Joined:
Jul 25, 2004
Messages:
736
37
Trophy Points:
28
Simple. Just find the HCF between the 2 Nos and if its anything other than 1 or -1 then they are co-primes. Isnt finding HCF a simple logic.

Joined:
Apr 4, 2005
Messages:
1,645
87
Trophy Points:
0
Occupation:
Programmer
Location:
Kolkata, India
In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1.

In the program below, I've used the gcf() function to check whether the GCF of the two numbers is 1.

Code:
```#include <stdio.h>
#include <conio.h>
int gcf( int n , int m ) ;
int lcm( int n , int m ) ;

int main()
{
int a , b ;
clrscr();

printf( "Enter two integers\n" ) ;
scanf( "%d" , &a ) ;
scanf( "%d" , &b ) ;

if(gcf(a,b)==1)
{
printf("The numbers are co primes");
}
else
{
printf("The numbers are not co primes");
}
getch();
return 0 ;
}

/*
gcf

Calculates the gcf (greatest common factor) for a pair
of integers.  If either number is zero, zero is returned.
Negative inputs are treated as if they were positive.
*/
int gcf( int n , int m )
{
if( n == 0 || m == 0 )
return 0 ;

if( n < 0 )
n = - n ;
if( m < 0 )
m = - m ;

/* subtract the larger from the smaller until they are equal */
while( 1 )
if( n > m )
n -= m ;
else if ( n < m )
m -= n ;
else
break ;

return n ;
}
```