In lecture class we saw a simple program to check primality of a number n by dividing it by numbers less than n. This is a little wasteful. It is easy to see that if n does not have a factor upto square_root of n then it is a prime number.
In this lab you are asked to write two methods in a class called Prime_Factorization. The outline of class is here Prime_Factorization.java, it contains some already defined methods.
Of the methods that you have to write, the first method pr should check primality of n by dividing upto square_root of n. The second method factors prints the factorization of a given number as below.
Command "java Prime_Factorization 100" should give as output:
"prime factorization of 100 is:
(2**2)*(5**2)"
The above output stands for (2 raised to the power of 2) multiplied by (5 raised to the power of 2). "**" stands for exponentiation and "*" for multiplication.
If you have written your program correctly it will easily work for numbers upto 5-6 digits long, but may be too slow to return any answer for 9-10 digit long numbers. However a resonable exploitation of observation mentioned in the first paragraph is likely to result in a program that works for the entire integer range of java. Here are some more valid runs:
java Prime_Factorization 152263109
prime factorization of 152263109 is:
(152263109)
java Prime_Factorization 2147483646
prime factorization of 2147483646 is:
(2)*(3**2)*(7)*(11)*(31)*(151)*(331)
Can you check factorization of the largest positive number represented in the integer type namely, 2147483647?