computer since java asgn

Page 1 of 3 2015-11-18

CPS 150/Fall 2015 Assignment 5 Generating a table of prime numbers

Assigned: Nov 18; Due: Nov 24, 11 pm (on Isidore) Cutoff: Nov 30, 11 pm

Instructor: Tamisra H. Sanyal

Concepts explored

• java.util.ArrayList for maintaining a growing list

• Functions

• Formatted output using printf

• Algorithm design beyond Brute Force

Description

This program generates a table of prime numbers. It asks the user how many prime numbers the user wishes to

generate. It populates an array with that many prime numbers starting from 2, then it prints the array nicely formatted.

See the sample output.

Input to the program: The program prompts the user for how many prime numbers the user wishes to generate. If this

number is less than 4 or greater than 300 the program should exit with an error message.

Output from the program: The program prints (to the output window) a list of prime numbers, 10 per line, and formats

the output columns right justified using 7 as the width of each field.

Basic algorithm: The program should test numbers for being prime and add only the prime numbers to the array

(maintained in an ArrayList). We could use a loop like:

while we do not have enough primes

if the current candidate number is a prime

add that number to the primes array

update the count of primes generated

end if

increment candidate number

end while

To check that a number n is a prime, we could use a brute force search for divisors from 2 up to n/2 (as in Lab 12). But

we can do this more efficiently by recognizing a few elementary facts about numbers:

• Except for 2, all other prime numbers are odd, so any even number > 2 can be rejected right away from being

prime.

• We only need to test using divisors that are ≤ √n and also are prime. A number that is not divisible by 5 is not

going to be divisible by 15.

We design a function (ok, method) with the following header:

static boolean isPrime(ArrayList<Integer> primes, int candidate)

This function will decide the easy cases first, by doing the following

// dispose of easy cases first

if (candidate < 2) return false; // numbers less than 2 are not prime if (candidate == 2) return true; // 2 is prime if (candidate % 2 == 0) return false; // even numbers > 2 are not prime

Then it will try out the divisors from the existing prime number list and if any divisor divides the candidate evenly it

returns false. The largest divisor it needs to try is mentioned above. If none of the divisors divide the candidate number

evenly then the loop should end, and the function should return true. This is similar to a search process.

Page 2 of 3 2015-11-18

The main function should declare an ArrayList to hold the required number of primes. It should be populated with the

first 4 prime numbers {2, 3, 5, 7}. As more prime numbers get added to the list, the .size() method can be used to

check the size of the list.

Design a function whose responsibility is to display the prime number array nicely. Its header could look like:

static void printArray(ArrayList<Integer> primes)

It should display the contents of the array 10 per line. A combination of print and println would be needed. Display each

number in a field of width 7 (use printf).

Here is a structure diagram to show which functions call which other functions:

main

isPrime printArray

Program style requirements

The program must contain a header comment block, each major section of the program must be identified by comments

(as in the labs) and the statements should line up properly. See the formatting in the book or my sample programs. Both

the program and the results should be nice to read.

To get full credit for the assignment, you must do the following:

• Use variable names that are meaningful

• Header block comments and section comments should be given

• Program text should be easy to read

• No extra-long lines in the program code.

• Program output should be easy to read and well –organized.

• Output window should be easy to read. Adjust the sizes of the panes to make that happen.

You will need to submit your source code and sample output pasted into a Microsoft word document. The Word

document’s file name should be youruserid_Asgn05.docx. Also submit the zipped project folder as before.

How to design the printArray function

Print each value in the array list with a fieldwidth of 7 (not println). Keep track of how many values are printed already.

Whenever that number is a multiple of 10, output the end-of-line character (println).

Here is a sample output:

Page 3 of 3 2015-11-18

Here is another, perhaps more interesting one: