Ass2

COP 3223 – Section 3

Assignment 2: Acme Cryptography Division



Problem Statement



The executives at Acme like you, you’re a go-getter. You get things done. That’s why you’ve been promoted to the extremely secretive (and well paying) cryptography division of Acme Corporation.



One of the biggest modern encryption algorithms is RSA. It relies on the fact that numbers are difficult to factorize. “Factorizing numbers is easy,” you think to yourself. “I’ve been doing that since elementary school.” Now is your big chance to impress your co-workers with your programming prowess. You are going to write a program that takes in a series of integers, N, and prints out all pairs of numbers (a,b), such that a times b equals N, such that a is less than or equal to b, and a is not equal to 1. Furthermore, you will print out a special message if the number is a prime.





Input Specification



Input will begin with a line single integer, T (1 <T< 10). On each of the following T lines, there will be a single integer, N (2 <N< 10,000,000).







Output Specification



For each test case, your program should first print a case header. This will begin with



Case X: N



Where X is the case number (from 1 to T), and N is the number which will be factorized. After this line, print a single line for each pair (a,b) such that a is less than or equal to b, a is not equal to 1, and a times b equals N. These lines should have the following format



(a,b)



These lines should be printed in increasing order of a. Be careful to print each pair exactly once. Also, note that there is no space between the comma and the second factor.



If there are no valid pairs of numbers, the number must be a prime. In this event, print the following statement:



This number is a prime!



After each case, print a blank line. For further clarification, refer to the sample I/O.







Sample I/O



Input:



4

9

10

11

12



Output:



Case 1: 9

(3,3)



Case 2: 10

(2,5)



Case 3: 11

This number is a prime!



Case 4: 12

(2,6)

(3,4)





NOTE: There is no space between the comma and the second factor



Deliverables



For your submission, please submit to webcourses2 a single file containing your source code. For scoring guidelines, please refer to the section labeled ‘Scoring Rubric’.



This assignment is due on webcourses2 at 11:59 PM, 12 February, 2013.





Scoring Rubric



This program is scored out of 20 points.



Coding Style (9) points

(1) Program contains a complete header comment (name, date, brief summary)

(1) Program maintains a reasonable use of whitespace

(1) Program uses clear, descriptive variable names

(1) Program reads in all values as integers

(1) Program contains a loop over T test cases

(1) Program contains a loop over N (or some function of N)

(1) Program does NOT prompt the user for input

(1) Program contains an if statement for handling the prime case

(1) Program contains at least one for loop



Correctness of Output (11) points (partial credit is possible)

(6) Printing of factor pairs

   (1) Program prints out all possible pairs in at least one non-prime test case.

   (1) Program prints out all possible pairs in most test cases

   (1) Program prints out all possible pairs in all test cases

   (1) Program does NOT print any duplicate factor pairs (i.e. (2,5) and (5,2))

   (1) Program does NOT print the trivial pair (1,N)

   (1) Program does NOT print any pairs where a times b does not equal N

(3) Formatting of factor pairs

   (1) All factor pairs list the smaller number first

   (1) Factor pairs are listed in increasing order of the smaller number

   (1) Factor pairs are each printed on a separate line

(1) Program correctly prints the primality message in the prime case

(1) Text is exactly of the specified form. Remember to print a new line after each case



NOTE: Pay careful attention to follow the output guideline exactly (punctuation, case sensitivity etc).