Programming Assignment # 2

Due: October 19.

This assignment has two parts: first, you will write a program that determines whether a number is prime. Next, if the number is not prime, print its prime factors. Recall that a number is prime if it is divisible only by itself and by 1.

The simplest method for testing whether a number *N*
is prime is to try to divide it by 2, 3, ..., *N*-1. If the remainder
is always different from zero, the number is prime. A better way is to
realize that you don't need to test all the up to *N*-1. Any number
that is not prime has to have a factor that is smaller than the square
root of the number. So we only need to check up to some number *X *with
*X*X *<= *N*.

The method we will implement for this assignment is called
the Sieve of Erasthothenes. The idea is to only test *N *against smaller
prime numbers, rather than all smaller numbers (why is this?). Here is
the idea: begin by making a table of integers 2 to *N.* Find the smallest
integer, *i*, that is not crossed out, print *i *, and cross
out all multiples of *i *(e.g. cross out *i,* 2*i, *3*i,*
...). When *i *> sqrt(N), that loop can stop. The second step of
finding the prime factors is trickier. Try to find an efficient way to
do it.

Write the program to run as an applet. The number to be tested is entered in a textfield. The result of prime testing, and the prime factors if there are any, are to be printed in the applet window.