## Homework 4

Computer Architecture I ShanghaiTech University
HW3 HW4 HW5

### Instructions

In this homework you will write a multi-threaded prime factorization program using C and Pthreads. The goal of this HW is to let you practice using pthreads and to learn about the implications of threaded programming.

The prime factors of a positive integer are the prime numbers that can divide the specific integer exactly. For example, `90 = 2 * 3 * 3 * 5`. Numerous algorithms have been developed for solving this problem, the simplist of which is the trial division algorithm, which tries to divide the number with all possible prime numbers.

#### Requirements

We will give the number of threads to run and a number to factorize to your program. Your program has to spawn the number of threads given to solve the problem correctly. You are required to use some variant of the trial division algorithm. E.g., using a wheel or a sieve in any part of the program is not allowed (and would lead to a 0 score for this HW).

#### Input

The input consists of two integers, `t` and `n`, which will be provided as arguments to your program, in that order.

`t` is the number of threads to run and satisfies `1 ≤ t < 100`. `n` is the number to be factorized and satisfies `2 ≤ n < 10,000,000,000,000,000,000`.

In case of errorous input your program should not produce any output on std but describe the error on stderr and exit with error code 13.

#### Output

The output should be in one line, consisting of all the individual prime numbers (sorted from smallest to biggest) and their power, i.e. the number of times they appear, connected with a carect `^` and separated with a single space. At the end there should be a line break `\n`.

#### Example Input and Output

Input line

``./factorize 5 90``

Output

``2^1 3^2 5^1``

### Submission

Put a single file called `factorize.c` in the root folder of the according gradebot repo.

• Your program has to be compiled using ` gcc -Wpedantic -Wall -Wextra -Werror -std=c89 `. It will be linked against pthread and math.