Project 1 Spring '09

CMSC 201
Programming Project One

Number Theory

Out: Wednesday 2/18/09
Due Date: Sunday 3/1/09, before 11:59 PM

The Objective

The objective of this assignment is to get you familiar with good design practices, writing in C in a Unix environment, using functions, and using separate compilation. It may also heighten your appreciation of mathematics.

The Background

The study of mathematics is separated into many fields. The one that tends to lead students to discover the beauty of mathematics is the field of number theory. This field deals with numbers and their relationships to each other.

The field of number theory has lead to discoveries such as :

Prime numbers -- those which can only be divided by themselves and one. Some special primes that you might find interesting are of the form 2^p - 1, where p is prime. These are called Mersenne Primes after the French monk Marin Mersenne who discovered them. The search for Mersenne primes continues. You can participate in the search for new Mersenne primes by joining GIMPS (the Great Internet Mersenne Prime Search). The 45th and largest known Mersenne prime is 2^43,112,609 - 1, a 12,978,189 digit number, was discovered on August 23, 2008 by Edson Smith at UCLA. On September 6, 2008 the 46th known Mersenne prime, 2^37,156,667 - 1, an 11,185,272 digit number was found by Hans-Michael Elvenich in Langenfeld, Germany. This was the first Mersenne prime to be discovered out of order since 2^110,503 - 1 in 1988.
Perfect numbers -- ancient mathematicians were interested in the relationship of a number and the sum of its divisors. A positive integer that is equal to the sum of its divisors (excluding itself) is called a "perfect" number. For example, the divisors of 6 are 1, 2 and 3. Since 6 = 1 + 2 + 3, 6 is a perfect number. The next three perfect numbers are 28, 496 and 8128. If the sum of the divisors is greater than the number, the number is called "abundant". If the sum of the divisors is less than the number, the number is called "deficient". Perfect numbers demonstrate some interesting properties -- all known perfect numbers end in 6 or 8; there are no known odd perfect numbers.
Squares -- many positive integers are considered geometric in nature. You learned about perfect squares in high school -- 1, 4, 9, 16. They are called "squares" because a group of 1, 4, 9 or 16 dots can be arranged in a square.
Triangular numbers -- Groups of 1, 3, or 6 dots can be arranged in a triangle and so these numbers are called "triangular" numbers. (If you've ever gone bowling, you'll recognize that 10 is also triangular.)
A more natural example arises when we consider a group of people who meet for the first time and everyone shakes hands with everyone else. The number of handshakes will be a triangular number.
Turns out that triangular numbers are the sum of consecutive integers.
To us this may just be an interesting relationship. To early Pythagoreans, it showed the mysterious nature of the universe and the way in which numbers and shapes have esoteric relationships.

Positive integers can be categorized in many different ways. This project will let you investigate some familiar and some new ways of looking at integers.

The Task

Your mission is to write a program that examines positive integers within a range that the user specifies and categorizes them as follows:

ODD or EVEN
PRIME or COMPOSITE -- a prime number is an integer greater than one that is divisible only by itself and one. Any number that is not "prime" is "composite". 1 is composite by definition.
PERFECT / ABUNDANT / DEFICIENT --- as described above
SQUARE -- as described above
TRIANGULAR -- as described above

Your program will also count the number of integers in the specified range that fall into each category and print a summary at the end. You should restrict the user to positive integers between 1 and 100000, inclusive. The ending number specified by the user should always be greater than or equal to the starting number s/he chose. You must validate the user's input. I guarantee that all input used to test your program will be of type int.

Your program MUST include the following functions. Do NOT change the function prototypes given below. You may choose to use more functions if you wish, but these are sufficient. All "predicate" functions below should return 1 for TRUE and 0 for FALSE. You have some flexibility in implementing the other functions. Choose wisely (and use #defines)

void PrintGreeting (void); 
     -- displays a suitable greeting to the user
int  GetValidInt (int min, int max); 
     -- gets an integer from the user between min and max, inclusive and 
        returns that valid integer.
void PrintTableHeading (void); 
     -- prints the heading of the table
int  IsOdd (int n);   
     -- a predicate function that returns TRUE if n is Odd and returns FALSE 
        if not.
int  IsPrime (int n); 
     -- a prediate funtion that returns TRUE if n is prime, and FALSE if not
int  CheckForPerfect (int n); 
     -- classifies n as "perfect", "abundant" or "deficient".  A different 
        value is returned for each different category.
int  SumDivisors (int n); 
     -- returns the sum of the divisors of n.
int  IsDivisor (int a, int b); 
     -- a predicate function that returns TRUE if a is a divisor of b, and 
        FALSE if not
int  IsSquare (int n); 
     -- returns TRUE if n is a perfect square, FALSE if not
int  IsTriangular (int n); 
     -- returns TRUE if n is a triangular number, FALSE if not
void PrintTableLine (int n, int odd, int prime, int perfect, int square, 
                     int triangular); 
     -- prints the information for one number on one line of the table
void PrintTotals (int first, int last, int numOdd, int numEven, int numPrime,
                  int numComposite, int numDeficient, int numPerfect, 
                  int numAbundant, int numSquare, int numTriangular);
     -- prints the summary of the number of different classifications found in
        the range specified.

You MUST use separate compilation for this project.

Since you will have to use a function from the C math library, you will not only need to #include <math.h> but you must also link using the -lm option. Here is how you'll need to compile your files :
gcc -c -Wall -ansi proj1.c
gcc -c -Wall -ansi numbers.c
gcc -c -Wall -ansi util.c
gcc proj1.o numbers.o util.o -lm

Sample Run

ecs225d-linux-01[257] a.out This program classifies positive integers as Odd/Even, Prime/Composite, Perfect/Abundant/Deficient, Square, and Triangular You will now get to choose the range of positive integers that you would like to see classified. Start with which positive integer ? Please enter an integer between 1 and 100000 : 1 End with which positive integer ? Please enter an integer between 1 and 100000 : 30 Int Classifications.................................... -------------------------------------------------------------------------- 1 Odd Composite Deficient Square Triangular 2 Even Prime Deficient 3 Odd Prime Deficient Triangular 4 Even Composite Deficient Square 5 Odd Prime Deficient 6 Even Composite Perfect Triangular 7 Odd Prime Deficient 8 Even Composite Deficient 9 Odd Composite Deficient Square 10 Even Composite Deficient Triangular 11 Odd Prime Deficient 12 Even Composite Abundant 13 Odd Prime Deficient 14 Even Composite Deficient 15 Odd Composite Deficient Triangular 16 Even Composite Deficient Square 17 Odd Prime Deficient 18 Even Composite Abundant 19 Odd Prime Deficient 20 Even Composite Abundant 21 Odd Composite Deficient Triangular 22 Even Composite Deficient 23 Odd Prime Deficient 24 Even Composite Abundant 25 Odd Composite Deficient Square 26 Even Composite Deficient 27 Odd Composite Deficient 28 Even Composite Perfect Triangular 29 Odd Prime Deficient 30 Even Composite Abundant Between 1 and 30 there were 15 Odd integers and 15 Even integers 10 Prime numbers and 20 Composite numbers 2 Perfect, 5 Abundant and 23 Deficient numbers 5 Square(s) and 7 Triangular numbers ecs225d-linux-01[258] a.out This program classifies positive integers as Odd/Even, Prime/Composite, Perfect/Abundant/Deficient, Square, and Triangular You will now get to choose the range of positive integers that you would like to see classified. Start with which positive integer ? Please enter an integer between 1 and 100000 : -10 Please enter an integer between 1 and 100000 : 20 End with which positive integer ? Please enter an integer between 20 and 100000 : 10 Please enter an integer between 20 and 100000 : 200000 Please enter an integer between 20 and 100000 : 50 Int Classifications.................................... -------------------------------------------------------------------------- 20 Even Composite Abundant 21 Odd Composite Deficient Triangular 22 Even Composite Deficient 23 Odd Prime Deficient 24 Even Composite Abundant 25 Odd Composite Deficient Square 26 Even Composite Deficient 27 Odd Composite Deficient 28 Even Composite Perfect Triangular 29 Odd Prime Deficient 30 Even Composite Abundant 31 Odd Prime Deficient 32 Even Composite Deficient 33 Odd Composite Deficient 34 Even Composite Deficient 35 Odd Composite Deficient 36 Even Composite Abundant Square Triangular 37 Odd Prime Deficient 38 Even Composite Deficient 39 Odd Composite Deficient 40 Even Composite Abundant 41 Odd Prime Deficient 42 Even Composite Abundant 43 Odd Prime Deficient 44 Even Composite Deficient 45 Odd Composite Deficient Triangular 46 Even Composite Deficient 47 Odd Prime Deficient 48 Even Composite Abundant 49 Odd Composite Deficient Square 50 Even Composite Deficient Between 20 and 50 there were 15 Odd integers and 16 Even integers 7 Prime numbers and 24 Composite numbers 1 Perfect, 7 Abundant and 23 Deficient numbers 3 Square(s) and 4 Triangular numbers ecs225d-linux-01[259]

Although your output need not be identical to the above, all information (including the greeting) must be present.

Submitting the Program

You must name your source file that contains main() and the other functions that are specific to this project proj1.c.
The file that contains the functions relating to number theory should be called numbers.c and its header file should be called numbers.h.
The file that contains utility functions, i.e. GetValidInt(), that you are likely to reuse in other projects, should be called util.c and its header file should be called util.h.

To submit your project, type the following at the Unix prompt:

submit cs201 Proj1 proj1.c numbers.c numbers.h util.c util.h

To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs201 Proj1