Linked Lists Solution

$30.00

Description

In Lab10 we used arrays to store the prime factors and their powers for a given integer N, N >= 1. Though it was easily done, but the implementation was not very elegant. In this lab, we will use linked lists to represent the prime factors and their powers, and practice linked list operations. Thus, the following structure should be adopted to make linked list for each prime factor of an integer N.

typedef struct factor {

// node for a prime factor

int

prime;

// prime factor

int

power;

// associated power

struct factor *next;

// pointer for the next prime factor

} FACTOR;

Using linked lists based on the structure defined above, please implement the following four functions as lab10.

  1. FACTOR *factorize(int N);

This function factorizes the input N into its prime factors and their associated powers, and returns a linked list that contains all these prime factors.

  1. FACTOR *GCD(FACTOR *A, FACTOR *B);

This function takes two linked lists of prime factors as input, and finds the Greatest Com-mon Divisor of these two inputs. Note that it returns a linked list of prime factors.

  1. FACTOR *LCM(FACTOR *A, FACTOR *B);

This function takes two linked lists of prime factors as input, and finds the Least Common Multiple of these two inputs. Note that it also returns a linked list of prime factors.

  1. void write(FACTOR *A);

This function prints out all the prime factors and their associated powers. In addition, it recalculates the product of all the factors and prints out at the end.

Your program should take two command line arguments as the inputs to your program, find their prime factors, their GCD, LCM, and then print them out. Examples of program execution are shown below.

  • ./a.out 100 225

A = 2^2 * 5^2 = 100 B = 3^2 * 5^2 = 225 GCD = 5^2 = 25

LCM = 2^2 * 3^2 * 5^2 = 900

  • ./a.out 24 35 A = 2^3 * 3 = 24

LCM = 2^3 * 3 * 5 * 7 = 840

Notes.

  1. Create a directory lab12 and use it as the working directory.

  1. Name your program source file as lab12.c.

  1. The first few lines of your program should be comments as the following.

/* EE231002 Lab12. Linked Lists ID, Name

Date:

*/

  1. After you finish verifying your program, you can submit your source code by

$ ee231002/bin/submit lab12 lab12.c

If you see a ”submitted successfully” message, then you are done. In case you want to check which file and at what time you submitted your labs, you can type in the following command:

$ ee231002/bin/subrec lab12

It will show the submission records of lab12.

  1. You should try to write the program as efficient as possible. The format of your program should be compact and easy to understand. These are part of the grading criteria.

2