V22.0101 ..... Homework 6 ..... Fall 2006
Primes

Assigned: Wed Nov 1
Due: Thurs Nov 9 at midnight.

The Sieve of Eratosthenes is an algorithm for finding all prime numbers less than or equal to a given number N. The idea is to test N only against smaller prime numbers, instead of all smaller numbers. We need an array from 2 to N, but arrays must start at 0 in Java so we start the array at 0 and just ignore or "cross out" the first two slots; thus the size of the array is N+1. Repeatedly do the following: find the smallest integer, I, that is not crossed out, and "cross out" all multiples of I (2I, 3I, etc), continuing until I > sqrt(N). For a reason that will be explained below, use an int array instead of a Boolean array, initialized to contain zeros, and when "crossing out" position K because K is a multiple of I, SAVE I in position K.

Write a program which implements the following, either as static methods or instance methods, as you prefer, and organized into classes as you think best.

• a method that, given N, implements the Sieve of Eratosthenes as just described, thus determining the prime numbers less than or equal to N.
  
  
• a method that uses the result of the sieve method to PRINT THE PRIME FACTORIZATION of a number C <= N. For example, the prime factorization of 12 is 3 x 2 x 2. Here is the idea: If C is not prime, you will find one of its prime factors, say P, in position C. For example, you might find 3 in position 12, since 3 was the last prime for which 12 was "crossed out". If you now divide C by P, you will get another factor of C, say Q. For example, if you divide 12 by 3 you get 4. Now by looking in the Q position, you will either find out that Q is prime, in which case you are done, or else you will find a prime factor of Q....and so on. For example in position 4, you will find 2, which is a prime factor of 4 and also of 12. In this way you can write a loop to print all the prime factors of C. QUESTION: does the output that you get change if you change the sieve loop so that it goes up to N instead of sqrt(N)? Explain why or why not in the program comments.
  
  
• a method that, given a number K, checks to see if K can be expressed as a SUM OF TWO SQUARES, A*A + B*B, where A and B are positive integers. Choose an efficient algorithm to search through the possible cases, and explain how it works in the comments.
  
  
• a main method that calls the sieve method ONCE, using a value for N which is entered by the user. Then, the program should do the following, for EACH K = 2 to N:
  • Print its prime factorization on one line of output.
    
    
  • If K is prime, print that K is prime and then call the sum-of-squares method to find out if K can be written as a sum of squares - if so, print what A and B are, and if not, print that fact. (The printing should be done by the main method, not the sum-of-squares method.)
  
  Make sure that the output is well organized so that it can be read easily.

Finally, how big N can your program handle in a reasonable amount of time? How big does this compare with the "brain-dead" methods for computing primes?