Assignment 24: Factoring a number

due Monday 4/29

Write a program that can factor any integer into its prime number factors.

For example, if the user enters 60 then a correct output would be

60 = 2 * 2 * 3 * 5

Your program must utilize at least one of two functions that you wrote in past assignments: prime (from Assignment 22) and divisible (from Assignment 17). Copy those functions into your new program as needed.

Here is one possible strategy you could use.

Input a number n.
Start by checking if n is divisible by 2.
- If n is divisible by 2, print out a 2, and store the remainder into n by doing n = n/2. Then, you must go back and check divisibility by 2 again (because there might be more than one factor of 2).
- If n is not divisible by 2, continue onward.
Now check whether n is divisible by 3, and so on for other possible factors. (You should use a loop for this. The first iteration of the loop would check for factors of 2, the second interation would check for factors of 3, etc.)
You can stop when, after dividing by a factor you've found, the number that remains is 1.

Test values for sample runs

2 60 98 360 499 667 2000 14641 30330 198147 999983 1022117 1048576 897100929 899999879 899999986

Extensions

For 5 of the 10 extension points: Make your program display any repeated factors as powers, as in this example.

360 = 2^3 * 3^2 * 5

For 5 of the 10 extension points: Choose a factoring method that works efficiently enough that your program can factor large numbers (like the three 9-digit test numbers) in less than a second (on neon, under typical conditions). If you believe you have achieved this kind of speed, demonstrate your program to me during class to receive these extension points.