In this exercise you are asked to write programs to factor a (positive) integer n into a p...

In this exercise you are asked to write programs to factor a (positive) integer n into a product of primes. (If n = 0, be sure to return an error message instead of going into an infinite loop!) A convenient way to represent the factorization of n is as a 2 × r matrix.

Thus, if

then store the factorization of n as the matrix

(If your programming language doesn’t allow dynamic storage allocation, you’ll have to decide ahead of time how many factors to allow.)

(a) Write a program to factor n by trying each possible factor d = 2, 3, 4, 5, 6, . . .. (This is an extremely inefficient method but will serve as a warm-up exercise.)

---

(b) Modify your program by storing the values of the first 100 (or more) primes and first removing these primes from n before looking for larger prime factors. You can speed up your program when trying larger d’s as potential factors if you don’t bother checking d’s that are even, or divisible by 3, or by 5. You can also increase efficiency by using the fact that a number m is prime if it is not divisible by any number between 2 and Use your program to find the complete factorization of all numbers between 1,000,000 and 1,000,030.

---

 (c) Write a subroutine that prints the factorization of n in a nice format. Optimally, the exponents should appear as exponents; but if this is not possible, then print the factorization of (say) n = 75460 = 22 • 5 • 73 • 11 as 2ˆ2 * 5 * 7ˆ3 * 11.

(To make the output easier to read, don’t print exponents that equal 1.)