Question

The greatest common divisor of two integers x and y is the largest positive integer that evenly divides both. For example, gcd(12,6)=6, gcd(21,14)=7, gcd(31,10)=1, gcd(55,25)=5

Recall that the gcd of two integers is gcd(a,0) = a gcd(a,b) = gcd(b, a%b) Create int gcd(int x, int y).

Assume that the two integers are zero or positive. Write the code as a pure function. Put it in a file gcd.c. Of course, you will need to test it.

The function Φ(n) counts how many integers 1 to n are relatively prime to n. Two integers x and y are relatively prime when gcd(x,y)= 1. So 5 and 12 are relatively prime, but 3 and 12 are not.

For example, Φ(1)=1, Φ(2)=1, Φ(5)=4, Φ(6)=3, Φ(8)=4, Φ(31)=30 Write a function int phi(int n) that computes this. Make this a pure function. Put it in its own file, phi.c. Write a driver that contains main() to test it. Put this in its own file phiTester.c.

C:\Source>gcc phiTester.c gcd.c phi.c

C:\Source>.\a.exe

Enter n: 259

Phi is 216

Turn in separate source files tau.c, tauSearch.c, phi.c and phiTester.c.

From poster: Please use comments, I want to see how it works!

Answer 1

// gcd.c

// function that calculates the gcd of x and y where x, y >=0
int gcd(int x, int y)
{

   int a, b;
   // check if both x and y are zero then return 0
   if(x != 0 && y!=0)
   {
       // determine which is larger
       // store the larger is a and smaller in b
       if(x > y)
       {
           a = x;
           b= y;
       }
       else{
           a= y;
           b=x;
       }

       int r=a%b; // calculate the remainder left when a is divided by b
       // loop that continues till we get b which divides a completely
       while(r!=0)
       {
           a=b; // assign b to a
           b=r; // assign the remainder to b
           r=a%b; // calculate the remainder left when a is divided by b
       }
   }else
       b=0;

   // gcd of x and y is stored in b
   return b;
}
//end of gcd.c

// phi.c

// function prototype
int gcd(int x, int y);

// function to count the number of integers from 1 to n that are relatively prime to n
int phi(int n)
{
   int count = 0, i;
   // loop that continues from 1 to n-1
   for(i=1;i<n;i++)
   {
       // if gcd of i and n = 1, increment count
       if(gcd(i,n) == 1)
           count++;
   }

   return count; // return the count
}
//end of phi.c

// phiTester.c : C program to input n and calculate the count of integers from 1 to n that are relatively prime to n
#include <stdio.h>
#include <stdlib.h>

// function prototype
int phi(int n);

int main()
{
   int n;
   // input of n
   printf("Enter n: ");
   scanf("%d",&n);
   // display the count of integers that are relatively prime to n
   printf("Phi is %d",phi(n));
   return 0;
}
//end of phiTester.c

Output: