Gaussian Numbers

Introduction

The Gaussian integers are complex numbers of the form a + bi, where a and b are integers. The numbers 1, -1, i, -i are known as the units. A Gaussian integer (a+bi) is called a Gaussian prime if and only if (a+bi) = (p+qi)(r+si) implies that (p+qi) or (r+si) is a unit. (Note that this implies the complex units are not Gaussian primes.)

If a real integer x s not a prime, e.g., x = y * z where neither y nor z are 1 or -1, then it is not a Gaussian prime. (For example, 6, 15, 289 are not Gaussian primes.)

What makes the Gaussian primes interesting is that the converse may not be true: for example 2 cannot be factored over the real integers, but 2 = (1 + i)(1 - i) neither of which is a unit so 2 is not a Gaussian prime. The integer 3 is a Gaussian prime, for reasons that will be apparent later.

The API you are to implement consists of 3 functions:

• Take a Gaussian integer z as an argument, and determine if it is a Gaussian prime. If it is not a Gaussian prime, factor it into Gaussian integers. Write the result to stdout.
• Take a magnitude M and compute all Gaussian primes a + bi such that 0 <= a <= M and 0<= b <= M. Write the primes to stdout.
• Take a magnitude M and draw a plot showing all the Gaussian primes that would be computed in Part 2. The plot should be in the form of text that you print to stdout.

Requirements

Inputs for your functions will come from tests cases written in main.c file. You can assume that input format will always be correct. That is, you don’t need to check the validity of input in your functions.

Output Format

For Mode 1, your output should be for the form:

-1 + 3i is not a Gaussian prime. Factorization = (1+2i)(1+i)
1 + 4i is a Gaussian prime.

Warning: Your output should be exactly in the form described above. Otherwise, you may lose points. Print only one factorization of the input if it is not a Gaussian Prime.

For Mode 2, your output should be of the form:

Primes with real and imaginary parts having magnitude less than or equal to 4 = {0 + 3i, 1 + 1i, 1 + 2i, 1 + 4i, 2 + 1i, 2 + 3i, 3 + 0i, 3 + 2i, 4 + 1i}

Warning: Your output should be exactly in the form described above. Otherwise, you may lose points. Pay attention to the order of sequence (ordered first by real component and then by imaginary component) and the commas! You should not put a comma at the end of the list. You will need to find a way to handle it. Print Gaussian primes only in the positive-positive quadrant.

For Mode 3, your output should be text, e.g., if M = 4

For M = 4;
4 0X000
3 X0X00
2 0X0X0
1 0XX0X
0 000X0
--01234

For z = a + bi, y-axis represents b values, and x-axis represents a values. Warning: Your output should be exactly in the form described above. Otherwise, you may lose points. Plotting Gaussian primes in the positive-positive quadrant is enough for correct result.

Design and implementation constraints

For Mode 1; you will need to write nested loops to use brute force in order to find if the input is a Gaussian prime or not. If not, you should print one of the factorization of the input.

To find that the input is not a Gaussian prime, you need to find 2 complex number where multiplication of these two complex numbers should be equal to your input (check the definition described above for more detail about Gaussian primes). That is, for input z where z = (a+bi)(c+di), you need to iterate over a, b, c, and d values to prove that z is not a Gaussian prime number.

For Mode 2; you should iterate over [0,M] for both a value and b values where z = a+bi For each a, b values, you need to check if (a+bi) is a Gaussian prime or not. If so, you should print the result. For better performance, you may want to use a 2D array. You can iterate over cell indexes, and put 1 if it is a Gaussian prime, 0 if it is not. Then, you can print your 2D array as described in previous section.

For Mode 3; you should do the same thing as you do for Mode 2. However, this time you will plot your result as described in previous section. If it is a Gaussian prime, you should print X, otherwise 0 (zero). Your output should be exactly in the form described above.