C program to compute Totient of a number

Share

In the field of number theory, the totient function of Euler is a computation that counts the number of positive integers up to a given integer n that are relatively prime to n.

#include <stdio.h>

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a % b);
    }
}

int totient(int n)
{
    int result = 1;
    for (int i = 2; i < n; i++)
    {
        if (gcd(i, n) == 1)
        {
            result++;
        }
    }
    return result;
}

int main()
{
    int n;
    for (int i = 0; i < 3; i++)
    {
        printf("Enter a number: ");
        scanf("%d", &n);
        printf("The totient of %d is %d\n", n, totient(n));
    }
    return 0;
}

Output

Explore further C programs here.

Share