SI 204 Spring 2017 / HWs


Homework 19: Practice with recursion

Name: _____________________________________________ Alpha: ___________________

Describe help received: ________________________________________________________

  • Due before class on Friday, March 3
  • This homework contains code to be submitted electronically. Put your code in a folder called hw19 and submit using the 204sub command.
  • This is a written homework - be sure to turn in a hard-copy of your completed assignment before the deadline. Use the codeprint command to print out your code and turn that in as well.

Assignment

  1. Circle one to indicate how you did for the reading assignment from Homework 17 before class on Monday:

    How carefully did you complete the reading? (Circle one)

    Not at all
    Skimmed it
    Read some
    Read all
  2. Circle one to indicate how you did for the reading assignment from Homework 18 before class on Wednesday:

    How carefully did you complete the reading? (Circle one)

    Not at all
    Skimmed it
    Read some
    Read all
  3. Given the following function prototypes:
    int foo(int a, double* b);
    void bar(int* c);
    and the following variable definitions:
    int x = 10;
    double y = 20;
    char z = 'z';
    Now for each of the function calls below, circle either "FINE" or "ERROR", and in case of an error, say exactly why there is an error.
    1. foo(x, &x) FINE ERROR
      Reason for error:
    2. foo(y, &y) FINE ERROR
      Reason for error:
    3. bar(&x) FINE ERROR
      Reason for error:
    4. bar(&z) FINE ERROR
      Reason for error:
    5. bar(foo(x, &y)) FINE ERROR
      Reason for error:
    6. foo(bar(&x), &y) FINE ERROR
      Reason for error:
    7. foo(foo(y, &y), &y) FINE ERROR
      Reason for error:
  4. Write a program called countprimes.c that reads two integers from the user and determines how many prime numbers are in the given range.

    You may copy and use this function to determine whether a number is prime:

    // Determines whether n is a prime number.
    // If it is, 1 is returned, and if not, 0 is returned.
    int isprime(int n) {
      if (n < 2) {
        // 2 is the smallest prime.
        return 0;
      }
    
      // try all possible divisors of n
      for (int fact=2; fact*fact <= n; ++fact) {
        if (n % fact == 0) {
          // n is divisible by fact, so not a prime
          return 0;
        }
      }
    
      // n doesn't have ANY factors, so it's a prime.
      return 1;
    }

    And you should write two recursive functions yourself to help with the task. (Which means, these functions should not have any loops and they they should make recursive calls to themselves):

    // Reads a single number from the terminal that is at least
    // as large as the given integer.
    // If the user enters a number too small, they will repeatedly
    // be prompted again and again until they enter a number that
    // is large enough.
    int getnum(int atleast);
    
    // Returns the number of primes between a and b.
    // The count is inclusive meaning that if a or be is a prime,
    // they should be included in the count.
    int countprimes(int a, int b);

    Here are a few example runs to demonstrate how your program should work. If you use the functions that you created above, your main method should be pretty simple!

    roche@ubuntu$ ./countprimes
    Enter a number at least 1: 10
    Enter a number at least 10: 20
    There are 4 primes between 10 and 20.
    roche@ubuntu$ ./countprimes
    Enter a number at least 1: 11
    Enter a number at least 11: 19
    There are 4 primes between 11 and 19.
    roche@ubuntu$ ./countprimes
    Enter a number at least 1: 20
    Enter a number at least 20: 10
    Too small!
    Enter a number at least 20: 10
    Too small!
    Enter a number at least 20: 21
    There are 0 primes between 20 and 21.
    roche@ubuntu$ ./countprimes
    Enter a number at least 1: -1
    Too small!
    Enter a number at least 1: 1
    Enter a number at least 1: 1000
    There are 168 primes between 1 and 1000.