Project: The Sieve of Erastosthenes
Everyone has seen the Sieve at some point in their education. Fewer have actually tried to use it to find prime numbers. Here's your chance to do so. This is a simple problem that can become fairly complicated and elegant with a bit of work.
THE SIEVE
This is an ancient algorithm for finding prime numbers. A prime number is a whole number whose only factors are one and itself. All other whole numbers that are not prime are known as composite numbers.
As an example, 4 is a composite number, Its factors are 1, 2, and 4. 16 is also composite, with factors 1, 2, 4, 8, and 16. 2 is prime, with factors 1 and 2. Similarly 3, 5, 7, 11 are prime. The number 1 is not considered a prime number, because it is its only factor - this is a special case.
Here's how the Sieve works. Let's say you were to write down all the integers from 2 to some integer N. Let's say N = 25 for example.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Start with 2, because you already know that 2 is prime (it's easy to see that it is prime). . But since all the multiples of 2 have 2 as one factor, all the multiples are composite. Cross them out.
2 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25
Find the next integer still in the list, it's 3. All the multiples of 3 must have 3 as a factor. That makes them composite and they must go. Cross out the multiples of 3. It's OK to cross out a number more than once if you need to.
2 3 X 5 X 7 X X X 11 X 13 X X 17 X 19 X X 23 X 25
The next integer is 5; take out its multiples.
2 3 X 5 X 7 X X X 11 X 13 X X 17 X 19 X X 23 X X
Keep going until you go all the way through the list of integers. When you are done, the numbers that are left are all prime. We are left with the prime numbers { 2, 3, 5, 7, 11, 13, 17, 19, 23 }.
Cool, huh?
THE PROBLEM
Please prepare a C program that implements the Sieve and finds the primes among the first N integers, which you enter via a prompt or the command line. This paper example shows the result for N = 25.
Write the integers to a file, ten primes per line, tab delimited.
Include a discussion file describing the project. In your discussion, include the following:
All the primes less than 50. You can include this without breaking the file-size bank in Latte.
The largest prime number less than 75,000, and the count of primes less than 75,000. I want you to show that you actually ran the program and got some results.
The largest prime you can find using your program. I will look for the most effective program design to obtain the greatest count of prime numbers. So look for ways to use your resources most efficiently. How many are enough to find? It's not unreasonable to find the first four billion or so primes without too much difficulty.
Your discussion of the problem and how development went.
SUBMISSION
Submit the following:
Source code for your program, ready to compile.
Discussion file.
I recommend creating a makefile if you know make. If you don't, we'll cover it later, so for now you must give me instructions on how to build your program. Later assignments will demand makefiles.
GRADING
Here's what I'm looking for:
Good clean code and the right amount of commentary.
A solution that uses an intelligent approach and makes good use of system resources.
Clean compilation with all warnings turned on (-Wall option).
Execution without crashing or dumping core.
Evidence of thoughtful design. Try to be smart about how you use system resources.
Thoughtful discussion.
SUBMISSION DO's and DON'Ts
Please submit a ZIP archive containing your files that I can extract and work with. Please do not submit individual files. Use conventional naming: source files should end in .c; headers in .h; a makefile should be named 'makefile'. Latte will only allow you to submit one file; it must be a ZIP.
Do not submit "projects" or directory trees from editors such as Eclipse. These tend to hide files in places that only the IDE knows about. Don't submit files that have been tested or edited on Windows; these will almost certainly break when compiled on a Linux or UNIX system.
OBJECTIVES OF THE ASSIGNMENT
This is not the most efficient algorithm for finding primes, but it will give you practice with memory allocation (malloc()) and basic I/O. It's not a particularly difficult problem, but there are several ways you can be wasteful and really turn it into a painful exercise. In particular, high values of N consume plenty of memory and CPU time. Give some forethought about how you will design and test the program before you dive in.
I am looking for you to use this assignment as a way to get grounded in C, work out any issues with your development environment, and get ready for more work later in the term.
For this problem, it's OK to use I/O functions in the Standard I/O library. We'll get into syscalls soon enough, and the syscalls won't give you too much of a benefit here.