- The Problem
- User's Guide
- Programmer's Guide
- Algorithm Design & Implementation
- Error Checking
- Testing
- Code Listing

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(N ^{2})*

**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(N ^{3/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 26.2 Testing correct one-output cases (3)

ella 43 % java PrimeEnter a positive integer ...3 2 There are 1 primes less than 36.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 1006.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 156.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)

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; } }