CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 2 (Due Thursday 7-Sep, at 10pm)


This lab has 2 required forms -- one to make groups and one to peer-review each others' groupwork (in terms of being great groupmates, not in terms of getting right answers).

Reminder: do not work on these problems alone -- only work on them together with your lab partners!

  1. numberLength [15 pts]
    Write the function numberLength(x) that takes a non-negative integer x and returns the number of digits in x. For example, numberLength(12) would return 2. Note: we will use this function in many of the following problems in lab2 and hw2!

  2. countMatchingDigits [20 pts]
    Write the function countMatchingDigits(x, y) that takes two non-negative integers, x and y, and counts the number of digits that match between the two integers. For examples, the pair (1234, 2071) has two matches, 1 with 1 and 2 with 2. The pair (2203, 1527) also has two matches, since each of the 2s from the first number match with the 2 from the second.

    Hint: In this and in future problems, you'll need to get individual digits from numbers. If you want, you can reuse your solutions to getKthDigit from lab1 and numberLength to do this.

  3. nthCircularPrime [30 pts]
    A circular prime is a number with the property that any rotation of that number's digits is prime. In this case, rotation refers to cycling the digits of a number; for example, the rotations of 1234 are 1234, 2341, 3412, and 4123. You can read more about this on the Wikipedia page. Single-digit primes are all circular, of course. To find the nth circular prime, you'll need to write isPrime and three other functions:

    1. rotateNumber [10 pts]
      This function takes a number, x, and rotates that number's digits by one place. This would turn the number 1234 to 4123.

    2. isCircularPrime [15 pts]
      This function takes a number, x, and determines whether that number is a circular prime. To do this, you'll need to check whether every rotation of the number is prime.

    3. nthCircularPrime [5 pts]
      This function takes a number, n, and returns the nth circular prime.

  4. nthEmirpsPrime [30 pts]
    This time, you'll be writing an nthPrime-type function without pre-determined helper functions! (Though writing helper functions is still a great idea and we encourage it.)

    Write the function nthEmirpsPrime(n) that takes a non-negative int n and returns the nth "Emirp prime", where an Emirp prime is a prime number which becomes a different prime number when its decimal digits are reversed. For example, 13 is an Emirp prime because when we reverse the digits we get 31, which is also prime. 2, 3, 5, 7, and 11 are all examples of primes that are not Emirp primes because they are the same prime when the digits are reversed. Here are the first several Emirp primes: 13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199,... So nthEmirpsPrime(0) returns 13.

    Aside: in case you missed it, emirp is prime spelled backwards. We didn't make this up (check out "emirp" on Wikipedia)!