CSE 3100 Systems ProgrammingHomework #3 Due: 10/01/2018Note that this assignment is due by midnight on October 1. You have more time to work on this assignment.Complete your work in the hw3 folder. Remember to pull, add, commit, and push. Do NOT add objectfile and executables in your repo.Exercise 1. (50 points) GCD and factorization. Finding factors for large numbers is a hard problem.However, the problem for small numbers is not hard. In this assignment, you implement a function thatfinds all prime factors of a given number, and a function that finds the greatest common divisor (GCD) oftwo numbers. The prototype of the two functions is:unsigned int ∗ f a c t o r i n t e g e r ( uns igned int n , unsigned int ∗ n f ) ;unsigned int ∗ f in d g cd (unsigned int ∗ pf1 , unsi gned int nf1 ,unsigned int ∗ pf2 , unsi gned int nf2 ,unsigned int ∗ n f ) ;factor integer() finds all prime factors of an unsigned integer n (and n > 1), stores them in a dynam-ically allocated array in non-decreasing order, and returns the starting address of the array. The numberof prime factors in the array is stored in an integer pointed to by nf. The product of all elements in thefactor array should be n. Return NULL if n is 0 or 1.For example, if n is 20, the returned array has three elements: 2, 2, 5, and *nf is 3. If n is 7, the returnedarray has one element: 7, and *nf is 1.find gcd() finds the prime factors of the greatest common divisor (GCD) of two numbers. The twonumbers are given as arrays of prime factors listed in non-decreasing order. pf1 is a pointer to the array ofprime factors for the first number and nf1 is the number of elements in the array. Similarly, pf2 is a pointerto the array of prime factors for the second number and nf2 is the number of elements in the array. As youmay have guessed, pf1, nf1, pf2, and nf2 are generated by calling factor integer(). If the GCD of thetwo numbers is greater than 1, the function returns the address of an array that stores the prime numbersof the GCD in non-decreasing order and *nf is the number of elements in the array. The function returnsNULL if the GCD of the two numbers is 1 (i.e., the two numbers are co-prime), or either of pf1 and pf2 isNULL.Your main work is to implement the factor integer() and find gcd() functions (and any helperfunctions you may choose to create). However, you will also need to add some lines of code near the end ofmain() to clean up.Here are some sample sessions of running the program. You can check with a calculator (e.g., usingPython and copy/paste!) if a number is indeed the product of all its prime factors and if the GCD candivide both given numbers.$./gcd-factor 64 19264=2 * 2 * 2 * 2 * 2 * 2192=2 * 2 * 2 * 2 * 2 * 2 * 3gcd(64,192)=2 * 2 * 2 * 2 * 2 * 2=64$./gcd-factor 123456789 1234567890123456789=3 * 3 * 3607 * 38031234567890=2 * 3 * 3 * 5 * 3607 * 3803gcd(123456789,1234567890)=3 * 3 * 3607 * 3803=123456789./gcd-factor 2000000000 19999999732000000000=2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 51999999973=1999999973gcd(2000000000,1999999973)=1=11Exercise 2. (50 points) Sparse polynomials. Many of the polynomials arising in practice are sparse,i.e., they have a number of non-zero coefficients that is much smaller than the degree of the polynomial. Inthese cases using an array representation is wasteful, and these polynomials are best represented as a linkedlist. The provided template code defines structures for representing polynomials as linked lists along withincomplete definitions of several functions that operate on them. Each function definition is preceded in thetemplate code by a comment detailing the expected functionality; read this carefully and follow all statedrequirements. Among others, these functions are required to read the input, dynamically allocate and freethe memory needed to store polynomials, compute the derivative of a polynomial, and compute the differenceof two polynomials. The full implementation of a function that prints a give polynomial represented as linkedlist is also provided; do not modify this function to preserve the output format shown below.Input: Your program should read from the standard input several pairs of whitespace separated integers,with each pair representing the coefficient and exponent of a monomial. You may assume that exponents arenon-negative and that monomials are given in strictly decreasing exponent order (in particular, the inputwill not contain multiple monomials with the same exponent). Coefficients are arbitrary integers and mayinclude zeros, however, only monomials with non-zero coefficients must be stored in the linked list. Themonomial with exponent 0 (constant term) is always present as the last monomial of the input, possiblywith a coefficient of 0. You may assume that all exponents and coefficients (both of input polynomials andof polynomials computed from them) fit within 32-bit signed integers.For example, the following input7 10 0 8 -4 3 -2 1 0 0represents the polynomial7x10− 4x3− 2x(note the two monomials with zero coefficients that are omitted).Output: The provided main() exercises the functions implementing polynomial operations and is expectedto produce output similar to the one listed below when your implementation is complete. Do not modify themain function except for including cleanup code required to avoid memory leaks.% ./polyEnter polynomial: 1 0P(x): 1P’(x): empty polynomialP(x) - P’(x): 1P’(x) - P(x): - 1P(x) - P(x): empty polynomial% ./polyEnter polynomial: 7 10 0 8 -4 3 -2 1 0 0P(x): 7 x^10 - 4 x^3 - 2 xP’(x): 70 x^9 - 12 x^2 - 2P(x) - P’(x): 7 x^10 - 70 x^9 - 4 x^3 + 12 x^2 - 2 x + 2P’(x) - P(x): - 7 x^10 + 70 x^9 + 4 x^3 - 12 x^2 + 2 x - 2P(x) - P(x): empty polynomial% ./polyEnter polynomial: 1 10 10 9 90 8 720 7 0 6 0 5 0 4 3 3 6 2 1 1 1 0P(x): x^10 + 10 x^9 + 90 x^8 + 720 x^7 + 3 x^3 + 6 x^2 + x + 1P’(x): 10 x^9 + 90 x^8 + 720 x^7 + 5040 x^6 + 9 x^2 + 12 x + 1P(x) - P’(x): x^10 - 5040 x^6 + 3 x^3 - 3 x^2 - 11 xP’(x) - P(x): - x^10 + 5040 x^6 - 3 x^3 + 3 x^2 + 11 xP(x) - P(x): empty