Csc 125 - Computer Science II, Programming in C++
Project 1 
Due: Thursday, September 7, 2006

Demonstrating two theorems of prime numbers.

Background

Mathematicians have proven a number of theorems about prime numbers.  The most important is called the "Prime Number Theorem", and it is used to prove that prime numbers do not become substantially rarer as the numbers get larger.  Specifically, the Prime Number Theorem states that the number of primes less than or equal to any integer n will always be close to the number n divided by the natural log of n.  The second theorem states that there will always be a pair of adjacent prime numbers, no matter how high you look in the positive integers.  A pair of adjacent prime numbers are two prime numbers that have a difference of 2.  In other words, they have exactly one even integer between them.

Sieve of Eratosthenes

The ancient Greek mathematician Euclid described a simple way to determine the prime numbers.  He imagined lining up a large number sticks, stuck upright in the ground, with a way to keep track of the number of each stick in line.  Then he would remove the first stick, because 1 is not a prime number, by definition.   Starting with 2,  he would knock over every second stick, because they must be divisible by 2 and therefore not prime.  He would go back to 2 and find the next stick standing, which would be 3.  So he would then knock over every third stick above 3, if it wasn't already knocked over, because they must be divisible by 3.  Going back to 3, the next stick still standing must be prime, because it was not a divisible by any of the previous primes.  That number would be 5, so he would knock down every fifth stick above 5.  He then finds 7 still standing and would knock down every seventh stick still standing above 7.  Then every 11th stick above 11, and so on.  After finding the first prime above the square root of the number of sticks originally stuck in the ground, all of the rest of the sticks still standing must represent a prime.  If the there were a composite number above the square root of the number of sticks, then one of its factors must be smaller than the square root.  Multiplying two numbers above the square root of the number of sticks would always produce a number greater than then number of sticks.

This algorithm is easily implemented on a computer by using an array to represent all the sticks.   Kicking over the sticks then becomes a loop within a loop.  The outer loop represents finding the next stick still standing, which must be a prime number, and the inner loop represents kicking over every prime_number_th stick in the rest of the array.

Assignment

Write a complete C program that first finds all the primes up to a very large number using the Sieve of Eratosthenes, implemented using an array.  Then walk the resulting array and print all the primes, with both the number of primes less than or equal to that prime and the calculation of:

that prime  /  the natural logarithm of that prime

Your output must be printed both to the screen.   The start of the output should look similar to this:

2              1                 2.8836
3              2                 2.7207   
5              3                 3.1066           
7              4                 3.5973          
11            5                 4.5873
13            6                 5.0683          
17            7                 6.0003
19            8                 6.4528           
23            9                 7.3353
29           10                8.6123

The first column is the prime number.  The second column is the number of primes less than or equal to that prime.  The third column is the number calculated by the equation above.           

Finally, walk the resulting array of prime numbers again, printing both, all of the adjacent prime number pairs.   A pair of adjacent prime numbers are two prime numbers that have a difference of 2.  In other words, they have exactly one even integer between them. The start of this output should look like this

                   3                         5
                   5                         7
                 11                       13
                 17                       19
                 29                       31

The maximum number to investigate, in other words the size of the array and the limits on the loops, must be in your program once only, as a constant at the top of the program.  You may either use C's #define or C++'s const int.  Using a single constant declaration will make it easy to change how high your program goes.  You will probably want to keep the value of this constant low, something like 100 or 1000, while you are developing the program.  You should try a much higher number when you are finished, to make sure the program will calculate up to a high number.  1,000,000 will be sufficient, but even that may take too long to print to the screen.  When I grade your project I will insist on seeing it work with a relatively large number of my choosing. 

Since all the even numbers except 2 are non-prime, can you implement the Sieve using odd numbers only?

 

Requirements

Your program must be written using good function design.  Each logical task in the program must be isolated into an appropriate function.  Your program must have a short, logically simple  int main(), that represents the entire logic of the program by calling various functions.  Specifically, the Sieve of Eratosthenes algorithm, the illustration of the Prime Number Theorem, and the display of adjacent primes, must each be in their own function.  You may have additional functions if you want.

Your program must also be properly indented and commented as shown in class, including function header comments. You must save your program in two files called  primes.c  and  prime.h  according to the standard practice for .c and .h files.  Your program cannot use any global variables.

Your program must be written for a Linux system, using ANSI C and good procedural C programming style.  Before grading, you must  check it on Parkland's Linux computers for proper operation.  You are not required or encouraged to use any ANSI C++ code, but you may if you want.  You may not use any non-ANSI C or C++ extensions.


 Grading

Project 1 is worth 16 points toward the final grade.  It will be graded according to the criteria on the Project 1 Grade Report. 

You will be given a hard-copy of your Grade Report during the Interactive Grading (see Date immediately following).  You are required to keep the Grade Reports for all your projects until you have your final grade at the end of the semester, in case there is a question about the grade of any of your projects.  

Date

Your project will be interactively graded on Thursday, September 7th.  On Tuesday, September 5th each student will sign up for a specific 15 minute period for grading on the following Thursday.  You may have your project graded before September 7th, if you wish, by making arrangements with the instructor. 

  
Back to Csc 125 - Computer Science II, Programming in C++
  Scott Badman   Office: B132   Phone: 353-2250   sbadman@parkland.edu  

Parkland College, 2400 W. Bradley Avenue, Champaign, IL 61821