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, 2i, 3i, ...). 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.