(20 points) Write a program that takes an integer as input and
outputs "prime" if the integer is prime and "composite" if the integer
is composite.
Notes:
- You may use any programming language you like. I need to be
able to test your program on the department UNIX machines.
- Your program should accept a number from standard input (the
keyboard) and write to standard output.
- For now, you should probably use a simple trial division
algorithm. Yes, it's too slow to be useful on big numbers.
You'll have a chance to code up a better algorithm in a few weeks.
- You need to be able to handle arbitrarily large integer input
(i.e., just using an int or long isn't good
enough). Every major language has support for this; in some
(e.g., Python), it's completely transparent.
- Some languages have a builtin or library routine, called
something like isPrime(), that does this all for you. You
can use this to test your program, but don't hand in code using it.
- Yes, there should be a prompt. No, I don't care what it says.
No, I don't care what you output when the input is "1". If you're
worrying about these sorts of questions, you're missing the point.
- You should hand in your code using hwsubmit.
The next two problems require Fermat's Theorem, sometimes called
Fermat's Little Theorem. (See pp. 217-218 of the Stallings book.)
Since this was not covered in class, I'm postponing these until we
discuss the theorem. If you want, you can do them now for extra
credit.