Saturday 27 September 2014

Finding co-prime numbers

 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.



#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;
}

2 comments: