Due 11:59 AM, Friday May 4

These problems are for extra credit. Any points you accumulate will be added to your program total. The first two are worth 5 points each, the third is worth 10, and the last is worth 20.

1. Write a program called palindromes1 that takes a single command line argument (call it n) and prints all integers from 0 to n whose squares are palindromes. Also print their squares. A palindrome is a number (or word) that is the same as its reverse. For example, 264 squared is 69696, which is a palindrome.

   Your program must include a function void reverse(char *s) that reverses the string s. It must also include a function int ispalindrome(long n) that returns 1 if n is a palindrome and 0 otherwise.

   Print a usage message to stderr if there is not exactly 1 command line argument.

2. Rewrite palindromes1 and call the new program palindromes2.

   This time, use a function long reverse(long n) that returns the reverse of a number. It should work in the following way. Note that taking a number mod 10 gives the low order digit, and dividing by 10 removes the low order digit. You can pull off the digits in reverse order by repeatedly taking the number mod 10 and then dividing by 10. For example, 9573 % 10 = 3. 9573 / 10 = 957. 957 % 10 = 7. 957 / 10 = 95. 95 % 10 = 5. 95 / 10 = 9. 9 % 10 = 9. Also, given a list of digits you can put them together into a number by starting with 0 and for each digit, multiplying the old number by 10 and adding the next digit. For example, given the digits 3, 7, 5, 9, the number 3759 = (((10 * 0 + 3) * 10 + 7) * 10 + 5) * 10 + 9.

   Rewrite the ispalindrome function to use this reverse.

3. Write a program called encrypt that takes a single command line argument that is an encryption key and uses it to encrypt text read from stdin. It will work as follows: If k is the encryption key, then the first character in the file will be XOR'd with k[0], the second character with k[1], the third with k[2], etc. When all the characters in the encrytion key have been used up, start over with k[0].

   The XOR operation (^ in C) has the following property. (a ^ b) ^ b = a, so XORing with the same value twice gives back the original value. This means that if you encrypt a file, then encrypting the encrypted file will restore the original. So encrypt is also decrypt.

   Print a usage message if no key is provided.

4. A prime number is special if all numbers obtained from it by deleting digits from either the left or right are also prime. For example, 317 is special because it is prime, but also 31, 3, 17, and 7 are prime. Write a program called special that finds all special primes less than 1000000. If fact, it turns out that these are all of the special primes (there are none larger than 1000000).

   Hints: Use a sieve to create an array of primes as in the factoring program. Then remove digits from the right side of the number until you get to 0, checking each number to see if it is prime. Then reverse the number and repeat, checking the reverse of each number for primeness. To see if a number is prime, use bsearch to search the array of primes for the number.