1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Check for co-primes

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

  1. meghna

    meghna New Member

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

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    734
    Likes Received:
    37
    Trophy Points:
    0
    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.
     
  3. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,646
    Likes Received:
    86
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    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 ;
    }
    
     

Share This Page