Introductory Programming In Java

HW 1

HW 2

HW 3

Homework 3

Factorisation and factorials

Choose one of the problems depending on how strong your mathematical background is:

The problem One

Write a Java program (in a class Factors) that takes an integer as the command line argument and then prints out the complete prime factorisation of that integer, with the factors in ascending order.

You do not have to do any other data checking. In other words, you may assume that the user will type in a non-negative integer, and it's OK if your program crashes if they type in something else.

Here is a sample run of the program. User input is in blue, system output in black. Your final output should be formatted exactly like this:


> java Factors 15
15 = 1 * 3 * 5

> java Factors 2008
2008 = 1 * 2 * 2 * 2 * 251

> java Factors 1999817
1999817 = 1 * 1999817
(that's a prime number)

When you will have completed this program, test it on a few numbers, large and small, until you are sure in its correctness.

Suggestion: You program needs at least one method other than main().

Hints:

Do not consider very large numbers for factorisation, for instance, use int or long types to work with (we need not to repeat the homework 2 exercise here).
It makes things a lot simpler when you realise that if you search for factors in increasing order, you will only ever find prime factors. So you don't have to test if the factors are prime. (Ponder how to prove this!)
We have probably not yet discussed how to write a Java program which can read from the command line. Take a look at the documentation for class Scanner, particularly the methods nextInt().

Extension task: Think about the program efficiency. Would it be more efficient only to test primes as factors? How could you do that without wasting more running time checking which numbers are primes? What if you just test odd numbers (since there are no even primes after 2)? Any other ideas?

The problem Two

Write a method to evaluate the factorial:

    
   static int factorial(int n)

Compute some cases by hand (or find a calculator on the computer somewhere to help you) to make sure that your method is working. By remembering homework 2, find out how big n can be before integer overflow occurs?

Note: The factorial of a positive integer n is

   
   n*(n-1)*(n-2)...*1

Moving on, the permutation function, p(n,k) is given by n!/(n-k)!. Using the factorial method of the previous exercise, write a method to calculate the permutation function. Once again, calculate some cases by hand and convince yourself that your program is working.

Assessment

You will get up to two marks, if you present a solution of at least one of the above problems during the next week lab.