COSC1020 Assignment.1 - Date: 08/09/1998

By: Last, First Name

ID: 123456789, Login: cs912345

Section: Registered in A, attending C

Table of Content

  1. The Problem
  2. User's Guide
  3. Programmer's Guide
  4. Algorithm Design & Implementation
  5. Error Checking
  6. Testing
  7. Code Listing

1. The Problem

Given a positive integer, print all primes less than it along with their count.

2. User's Guide

To run this program, type: java Prime at the O/S prompt. The program will prompt you to enter a positive integer. Once entered, the program will display all prime numbers less than your entry, if any, along with their count. If your entry is not positive, an error message will be printed and the program will end. The program cannot handle non-integer inputs, and will crash (with an exception) if such an input is encountered.

3. Programmer's Guide

The program exposes one boolean method called isPrime which can be used to determine if a given number is prime. See the documentation comments for details. Note that the method returns false if the passed parameter is less than 2 because, by definition, prime numbers cannot be less than 2.

4. Algorithm Design & Implementation

I used stepwise refinement to design an algorithm. At the top level, my algorithm consists of two steps:

1. Input and validate an integer N
2. Print all primes less than N along with their count

Step number 1 can be refined as follows:

1.1 Prompt the user
1.2 Read N
1.3 If N is not positive then print a message and end.

Step number 2 can be refined as follows:

2.1 For each integer between 2 and N-1 (all potential primes)
2.2 If it is prime then print it

Step number 2.2 can be refined further: Given an integer x greater than 1:

2.2.1 For each integer i between 2 and x-1 (all potential divisors)
2.2.2 If i divides x without a remainder then x cannot be prime; exit
2.2.3 If all the examined integers don't divide x, then x is prime.

We observe that step 2.2 is useful in many contexts and can be reused in other programs, so we implement it as a separate public method.

Complexity: Step 2.2 is linear; O(N). And since our program invokes it about N times, its overall complexity is quadratic; i.e. O(N2)

Note: The program complexity can be improved by noting that step 2.2.1 needs only examine integers between 2 and the square root of x. If this improvement is incorporated, the overall complexity becomes O(N3/2).

5. Error Checking

The program checks for non-positive integer entries and responds to them with an appropriate error message. It does not, however, handle non-integer inputs and will thus crash with a invalid integer IOException.

6. Testing

6.1 Testing correct boundary cases (1 and 2) 
	ella 41 % java PrimeEnter a positive integer ...1
	There are 0 primes less than 1
	ella 42 % java PrimeEnter a positive integer ...2
	There are 0 primes less than 2
6.2 Testing correct one-output cases (3) 
	ella 43 % java PrimeEnter a positive integer ...3
	2
	There are 1 primes less than 3
6.3 Testing correct many-outputs cases (10 and 100) 
	ella 44 % java PrimeEnter a positive integer ...10
	2
	3
	5
	7
	There are 4 primes less than 10
	ella 45 % java PrimeEnter a positive integer ...100
	3
	5
	7
	11
	13
	17
	19
	23
	29
	31
	37
	41
	43
	47
	53
	59
	61
	67
	71
	73
	79
	83
	89
	97
	There are 25 primes less than 100
6.5 Testing a correct case but with a leading zero 
	ella 50 % java PrimeEnter a positive integer ...000015
	2
	3
	5
	7
	11
	13
	There are 6 primes less than 15
6.5 Testing incorrect non-positive cases (0 and -5) 
	ella 46 % java PrimeEnter a positive integer ...0
	This number is not positive!
	ella 47 % java PrimeEnter a positive integer ...-5
	This number is not positive!
6.6 Testing incorrect non-integer cases (a real and a string) 
	ella 48 % java PrimeEnter a positive integer ...12.5
	java.io.IOException: invalid integer
		at java.lang.Throwable.(Compiled Code)
		at java.lang.Exception.(Compiled Code)
		at java.io.IOException.(Compiled Code)
		at java.lancs.BasicIo.readInteger(Compiled Code)
		at Prime.main(Compiled Code)
	ella 49 % java PrimeEnter a positive integer ...non-integer
	java.io.IOException: invalid integer
		at java.lang.Throwable.(Compiled Code)
		at java.lang.Exception.(Compiled Code)
		at java.io.IOException.(Compiled Code)
		at java.lancs.BasicIo.readInteger(Compiled Code)
		at Prime.main(Compiled Code)

7. Code Listing

import java.lancs.*;
import java.io.*;

/**
  * Displays all primes less than a given integer.
  *
  * @author Me!
  *
  */
public class Prime {

  /**
    * Prompts for and inputs a positive integer, and prints all
    * primes less than it along with their count. 
    * Displays an error message if the entry is not positive.
    * @exception IOException if the entry is not an integer
    */
  public static void main (String[] args) throws IOException {
    
    // ----------------------------Prompt and Input an integer
    BasicIo.prompt("Enter a positive integer ...");
    int num = BasicIo.readInteger();

    // ----------------------------Validate that num is positive
    if (num <= 0) 
       System.out.println("This number is not positive!");
    else {
       // ----------------------------Check all potential primes
       int count = 0;
       for (int candidate=2; candidate < num; candidate++) {
           if (isPrime(candidate)) {
              count++;
              System.out.println(candidate);
           }
       }
   
       // ----------------------------Display #of primes found
       System.out.println("There are " + count + " primes less than " + num);
    } 
  }    
  /**
    * Returns true if the passed integer is prime
    * and returns false otherwise.
    * Pre: x is positive
    * @param x the integer to check if prime
    * @return true if x is prime and false
    *         otherwise
    */
  public static boolean isPrime (int x) {
    if (x < 2) return false;           // 
    for (int i=2; i < x; i++) {        // for each i in [2,x)
        if (x % i == 0) return false;  // x not prime if i divides it
    }
    return true;
  }
}