CSE142

Homework #3

The Prime Directive

Electronic turn-in for Part A due: Wednesday, April 25, 10:00pm
Paper receipt due in section Thursday, April 26.

Electronic turn-in for Part B due: Monday, April 30, 10:00pm
(Two points extra for final turn-in by Sunday, April 29, 10:00pm)
Paper receipt due in class Monday or Wednesday, April 30 or May 2.

Goals The Task Background Specification Sample Runs Supplied code and files Your Writeup Guidelines, hints and help Submission Extras Announcements

If there's one thing that gets a computer scientist's heart racing faster than powers of two, it's prime numbers. Bowing to the concerns of academic diversity, this time around we'll study prime words rather than just prime numbers.

Goals

This assignment is designed to give you more work with loops, using several different patterns. You should also get a chance to use some complex conditionals. Finally, we hope you'll get a feel for how useful a good functional decomposition and careful design documents can be in making the actual programming part of a problem easier.

The Task

Numbers can be expressed in many different "bases"¹. Base 2 is regularly encountered in computer science because it uses only the digits 0 and 1. Base 10 is the common base used by we ten-fingered humans. For bases larger than 10, we use letters to express the extra digits (so, base 16 uses the digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F, where -- for example -- C represents 12). In base 36, every single letter of the alphabet represents a digit! So, every word is a number.

Your job: write a program that determines whether words are prime numbers in base 36.

Background

We've provided some background on prime numbers and numbers in different bases that might help you get up to speed.

Specification

Your program should read a series of words from the user. It should treat each word as a base 36 number and check whether that number is prime. If it is, it should print out a line saying "PRIME"; otherwise, it should print out "composite".

In particular, a word is a series of uppercase letters ('A' through 'Z') and digits ('0' through '9'). Each word will end with the end of the line ('\n'). Your program should stop reading words when it reads a line beginning with a '0'.

If your program ever encounters an illegal character (not an uppercase letter or digit or the '\n' at the end of a line) or word (too large to store in an int), it should print an explanatory message and halt by calling the function exit².

Sample Runs

Here are a few sample runs to give you an idea of what we want. Note that your program must follow this input/output style precisely this time!

Welcome to the prime word tester. Testing words in base 36. Enter a series of words. One per line, please. FOOD PRIME DRINK composite FRENCH composite LATIN PRIME 0ANYTHING Stopping. Welcome to the prime word tester. Testing words in base 36. Enter a series of words. One per line, please. SUMMAT composite MUCH2LONG That number is too large. Welcome to the prime word tester. Testing words in base 36. Enter a series of words. One per line, please. AtoZ Invalid character: 't'.

Supplied Code and Files

There is no supplied code with this assignment! You'll be writing this one on your own from scratch. Purely to help get you started, however, we are providing an empty MSVC workspace as a self-extracting archive.

You may use the debug.c and debug.h files from your previous homework (once again, do not submit them). You may also base your new program on previous ones to help get the "boilerplate" right.

There is also no sample solution this time! Use the example runs above to help you understand the problem.

The Missing Week

This assignment was originally supposed to be two weeks long, but to leave room for HW#4 and HW#5, we've cut it down to one week. Therefore, we're supplying you with all the work you would have done in that missing week! This is design work that you should understand before moving on with the assignment:

Your program must conform to the call graph and function descriptions listed here. However, you are free to add more functions if you believe they are needed.

Your Writeup

As with all assignments, you should include a text file in your submission called README.txt which describes your project. We have supplied a starter README that includes the questions below. As always, include the following standard info: your name, your student ID, your section, approximate hours spent on the assignment, and an acknowledgment of any help you received (other than the lectures/sections, the staff, or the course textbook). Note: acknowledging cheating does not stop it from being cheating!

For this assignment, we also require answers to two sets of questions. The first are pre-project questions that you should think about before starting the project. The second are post-project questions you should answer when you are done.

Pre-project questions:

Imagine a way to test each function to make sure it works. Pick two functions and briefly describe how you will test each one.
Choose and write down an order to implement the functions in this project. Briefly explain why you chose that order.
Which function do you think will be the hardest to write? Why?

Post-project questions

Which function was the hardest to write? Why?
Were most of the individual functions hard or easy to write? Did starting with a functional decomposition and design documents make them easier or harder?
Write at least three words you found that are prime.
What's the most insightful or interesting question you thought of, asked, or heard asked about this assignment? If it was a question you heard, make sure you attribute the source! Explain briefly why this was such a good question and what you think the (an?) answer is.
What did you enjoy about this assignment? What did you hate? Could we have done anything to make it better (either the assignment itself or the way we handled handing it out, clarifying it, or turnin procedure)?

Submission

Part A is just the function prototypes for your program. You should submit this by writing up prototypes for each of the functions described in the list of functions. Then, write an empty main function (just put empty braces after it { }) and empty implementations of each of the functions (just use empty braces for them as well). YOU DON'T NEED TO WRITE ANY CODE IN FUNCTION BODIES FOR THIS PART!!! Turn this in with the HW#3A turnin form. This part will be graded on participation; so, make sure you bring your receipt to section!!

Part B is the full homework assignment, including the README. Use the HW3B turnin form to turn in the assignment. Do not submit the debug.c and debug.h files! You should neither change nor submit these; we will provide copies on the turnin server.

Looking for more?

Have you beautifully reworked your code until it makes you cry with joy just to read it, written a Shakespearean sonnet using only prime words, and tired of playing LMAD against yourself? First, turn in a working version of your code. Then, try these ideas for further fun.

Base 36 uses all 26 letters of the alphabet, but there are plenty of words we can spell without every single letter. Try writing a program that prompts for a base and then interprets words as coming from that base (as long as they only use appropriate digits). For example, LUKE is prime in base 37.. but I'm sure his students could tell that just by looking at him.
Prime numbers are great, but there are other interesting properties of numbers. Write a program that tests for "perfect" word-numbers (the sum of all the divisors except the number itself is the number.. 6 and 28 are both perfect), "perfect square" word-numbers (any number with an integral square root like 4, 25, or 100), or "perfect cubes", etc.
This is all a super start, but what we really want is a list of prime words, right? Figure out a way to make a list of prime words. There are at least two ways to approach this!

Finished with the assignment and all of the above suggestions? Make up some questions for the final exam!

Footnotes:

Somehow we resisted the primal urge to name the assignment "All your base (36) are belong to us." Strive to resist the urge yourself!
exit is a function found in the library stdlib.h. It takes a single argument which should be 0 for success or 1 for failure. When executed, it completely halts your program just as if you had returned from main.
Stylistically, it's really not good to exit from all sorts of different places around your program. As an exercise, you might try setting up special values to indicate errors for all of your functions that would otherwise just call exit. Then, you can eliminate the need for the exit function entirely.