Problem: Two integers a and b are said to be relatively prime or co-prime if the only positive integer that evenly divides both of them is 1. That is, the only common positive factor of the two numbers is 1. This is equivalent to their greatest common divisor being 1.

Solution:

Solution:

#include<stdio.h>

int gcd(int a,int b)

{

if(a%b==0)

return b;

else

return gcd(b,a%b);

}

int main()

{

int n,i,count=0;

scanf("%d",&n);

for(i=1;i<=n;i++)

{

if(gcd(n,i)==1)

count++;

}

printf("%d",count);

return 0;

}

Programming Geek |

Source: programmaniaa blog.

*To get the more, view the [TCS] Finding co-prime numbers (CodeVita) Problem [Solved]. These are only for reference purpose.