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.

Pthreads stands for POSIX Threads and is the implementation of POSIX compliant threads on UNIX-like platforms.

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.

Grading

Gradebot will use a small number to test your program. If your output is wrong you will receive 0 pts! Gradebot will show you how much time your program took. This way you will have a rough estimate how fast you are compared to the other students. But keep in mind that the gradebot is a shared resource, so those values might differ a lot.

In the end we will run every program on a fast computer. The speed of each program will be noted.
The slowest 30 percentile and below will receive a score of 85%. The fastest 20 percentile will receive a score of 100%. All other programs will get a score that is linearly scaled between the fastest slow program and the slowest fast program.

Notes

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

Write meaningful comments in English in your code! (-20% if you violate this rule).

The size of your programs source cannot exeed 6KB.