CSC 115 Program #7
Fall 2013
Due: November 20
A prime number is an integer greater than 1 that is divisible only by 1 and itself. A composite number is an integer greater than 1 that is not prime. That is, a composite number has at least one divisor other than 1 and itself.
The Sieve of Eratosthenes is an algorithm for computing all the prime numbers within a given range of values. It works by a process of elimination. For example, we can compute all the prime numbers between 0 and 1000 by this process:
- Make a list of all the candidate numbers.
- Mark out all the multiples of 2.
- Mark out all the multiples of 3.
- Mark out all the multiples of 4.
- Likewise, mark out all the multiples of all the integers lower than 1000.
- All the numbers that remain are prime numbers.
Write a program that uses the Sieve of Eratosthenes to compute all the prime numbers less than 10,000. Output your list of prime numbers to an output file called primes.txt.
The Sieve of Eratosthenes is attributed to Eratosthenes of Cyrene, a Greek mathematician of the 3rd century BC. He is also known for using astronomical observations and geometry to compute the circumference of the earth to an accuracy of 2%.
Implementation Details
Use an array of 10,000 Boolean values to represent the list of numbers. Initialize all the array elements to true. To “mark out” a number, reset the corresponding array element to false.
You should write these functions and include them in your program:
void initialize(bool primeList[]);
void markOutComposites(bool primeList[]);
void outputPrimes(ofstream &outFile, bool primeList[]);
The Sieve of Eratosthenes can be implemented with a simple, “brute force” algorithm that works correctly but is very slow due to a lot of unnecessary “marking out” of values that have already been marked out. With some careful, clever thought and clever coding, you can reduce the redundancy to make your program much faster.
Instructions for Turning in Your Project
I will not grade your project, and you will receive a score of 0, if you do not comply with these instructions. You must turn in all materials by the date and time listed at the beginning of this handout. Your submission is not complete—and I will not grade it—until you have turned in all the required materials. Anything that is not turned in by the deadline will be marked at least one day late and will receive a grading penalty as specified in the syllabus.