SOLUTIONS FOR THE MIDTERM PROGRAMMING ASSIGNMENT. Problem 1: Implement division using only addition and subtraction. // returns n/k for positive integers n, k // for other values of n, k the behavior of this function is undefined int divide( int n, int k ){ int count = 0; while( k <= n ){ // count how many times k "goes" into n, i.e. // can be subtracted from n withot getting a negative n = n - k; count++; } return count; } ----------------------------------------------------------------------- Problem 2: Factor an integer. int n, p; cin >> n; cout << n << " : " ; // print the number itself while( n > 0 ){ // end the loop if the input is negative if( n == 1 ) // this is a special case: 1 is never printed otherwise cout << 1 << endl; else { p = 2; while( n > 1 ){ // n will be changing throughout this loop while( n % p == 0 ){ // p divides n cout << p << " "; n = n/p; // remove a copy of p from n } // after this loop all copies of p have been "divided out" of n, and // p will be printed as many times as it divides n p++; // go to the next number that might divide n (see NOTE) } cout << endl; } // enter a new number cin >> n; } NOTE: Not only primes, but ALL numbers up to the actual largest divisor of n will be tried as values of p . This may seem to be a bug, because we only want to print the prime divisors of n . However, NONE of non-prime divisors will be printed. To see why this is so, consider the following example: take n==120 and trace the algorithm starting with p = 2. n will be divided by 2 for as long as what remains is divisible by 2, i.e. 3 times ( 120 = 2*2*2*3*5 ). After this n==15. Then it will be divided by 3, so that n==5. The next p to try is 4=2*2, a non-prime number. BUT, all 2's have already been "divided out" of n . And so for each non-prime value of p all of the primes that compose p will be "divided out" earlier. So no non-prime divisor p will ever enter the inner while loop. Notice how the names n and p get re-used on every iteration. This is a very common technique. ----------------------------------------------------------------------- Problem 3: Here's my program, complete with testing. You may disregard the testing part and go directly to the function num that does the transformation. #include #include #include // random, srandom #include // srandom is seeded with current time // DISCLAMER: This is neither the shortest, nor the most // elegant way of solving the problem. // Constants for testing: Declare any parameters of your program // as const at the top. Leaving unexplained numbers in your code // is bad style. const int MAX_NUMBER = 999999; // this is the largest number // for which the output is correct const int ALL_UP_TO = 2000; // test all numbers up to this one const int RANDOM_TESTS = 100; // the number of random tests to run string upto20[] = { "zero", "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine ", "ten ", "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " }; string tens[] = { "NaN", "NaN", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " }; // the first two entries should never get printed string num(int); string num3(int); int main(){ for( int i=0; i <= ALL_UP_TO ; i++) cout << i << " : " << num(i) << endl; // srandom seeds the pseudo-random number generator. It is usually // seeded with current time (expressed in seconds since 00:00:00 // Jan 1, 1970), which is returned by the system call time(NULL) int x; srandom( (unsigned int) time(NULL) ); for( int i=0; i < RANDOM_TESTS ; i++ ){ x = random() % MAX_NUMBER; cout << x << " : " << num(x) << endl; } return 0; } // takes a number and returns the string corresponding to that number string num( int n ){ if ( n == 0 ) return "zero"; // this is a special case, because // "zero" doesn't appear otherwise string result = ""; int thousands_part = n / 1000; // separate the thousands if( thousands_part != 0 ) result += num3( thousands_part ) + "thousand "; result += num3( n % 1000 ); // the other part ( < 1000 ) return result; } // process a number with no more than 3 digits string num3( int n ){ string result = ""; int hundreds_place = n/100; if( hundreds_place != 0 ) result += upto20[ hundreds_place ] + "hundred "; int last_two = n%100; if ( last_two != 0 ){ // don't print zero if ( last_two < 20 ) result += upto20[ last_two ]; else{ // n >= 20 subdivide into tens and units int tens_place = last_two/10; if( tens_place != 0 ) result += tens[ tens_place ]; int units_place = last_two % 10; if ( units_place !=0 ) result += upto20[ units_place ]; } } return result; }