Assignment

Create a standalone Java program that can find the prime factors of an integer. Use the Java BigInteger class rather than an int type or the Integer type to allow for much larger numbers. [You may implement this in C++ or python as long as those languages have an equivalent class for very large integers.] Thus, a user should be able to enter: • 123456789 And get this result: • 123456789: = 3 * 3 * 3607 * 3803 That is, there is one input to the program, a positive integer that can be very large. The result is the prime factorization of that number. Note that if a particular prime divides the original number multiple times, that prime should be listed multiple times (as with the factor 3 in the example above.) You can use a brute force algorithm to do that. That is, to find the prime factors of N, you can just try every prime number that is less than or equal to ? to see if it divides N. (Do you see why you only need to go up to ? ?) You can use the BigInteger method isProbablyPrime when checking possible divisors. I have provided a method to find the square roots of a BigDecimal. You may use that. Of course, you will convert your answer to a BigInteger by rounding. There are methods in the BigInteger and the BigDecimal classes to manipulate these types.

For this phase, change the client and server design to allow for the task to be divided among several servers. For example, you can start 4 servers running on ceclnx01. (Let's call them server A, B, C, D.) The client gets the number from the user. Then, it sends this to server A which divides the range to be explored into 3 pieces. Server A then sends to server B the first third of the range, server C gets the second third of the range, and server D the remainder of the range. That is, if the number to factor is 123456789, we will need to search for prime factors between 2 and 11,111 (the square root of 123456789). The server B would look for prime factors between 1 and 3703; server C from 3704 to 7407, and server D from 7408 to 11,111. Then server A would accumulate the results and send them back to the user.

The jobs of server A would be to initiate 3 socket connections. Then it would wait for server B's response; then wait for server C to respond; and finally wait for server D to finish. Note that this is appropriate in this case since we cannot finish the task until all 3 are completed. For example, if server D happens to finish first, we cannot proceed until the other two servers are complete. So making us wait for the results from server D even though the results are ready does not slow the overall process. The last step for server A is to collect all of the data from the other three, order them appropriately, and send the results to the client.

If you want to use 5 servers, then you would divide the input into 4 pieces. The more servers that you use, the faster that this should be.