logic: Two integers m and n are said to be co-prime if their GCD is 1.
/* c program to print the number of integers
that are less than or equal to ‘n’ and co-prime to ‘n’ */
#include<stdio.h>
int gcd(int,int); /* function prototype */
int main()
{
int n;
printf("n: ");
scanf("%d",&n);
int i,count=0;
for(i=1;i<=n;i++)
{
if(gcd(n,i)==1) /* if i is co- prime to n */
{
count++;
}
}
printf("%d",count); /* prints no.of co-primes */
return 0;
}
int gcd(int a, int b) /* function for gcd */
{
int t;
while(b!=0)
{
if(a<b)
{
t=a; /* t is temporary variable */
a=b;
b=t;
}
t=a;
a=b;
b=t%b;
gcd(a,b);
}
return a;
}
Sample input and output:
input:
n: 5
output: 4
