Operational Objectives: Define and implement the class Prime and deliver the code in two files prime.h and prime.cpp along with a makefile for the supplied test harness.

The Sieve of Eratosthenes

Assume that b is a vector of bits indexed in the range [0 ... n). Denote the "value" of bit k by b[k]. The Sieve of Eratosthenes is a process that operates on a bit vector b, as follows:

Begin with a bitvector b indexed in the range 0 k < n. Our goal is to unset bits for all composit numbers up to n, so that b[k] = 1 if and only if k is prime.

Initialize b by setting all bits.

Unset b[0] and b[1] (because 0 and 1 are not prime).

For k between 2 and the square root of n, stepsize 1: if b[k] is set for j between k + k and n, stepsize k: unset b[j]

Stop.

In short, unset the bits of all multiples of primes less than the square root of n.

Assertion 1. After invoking the sieve algorithm, an integer k in the range [0 ... n) is prime iff b[k] = 1.

The assertion is proved by mathematical induction. The base cases k = 0,1,2 are each easily checked by following the first few lines of the process. For the inductive step, assume the assertion is true for all index values less than k. If b[k] = 0 then there was an instance of k = ab which resulted in unsetting b[k], so clearly k is composit. If b[k] = 1 then there was never an instance of k = ab with a prime and a² k. But that is enough to prove that k is prime, because a composit number always has a factorization of the form ab with a b (by just writing the smaller factor first) and then we would have k = pq where p is a prime factor of a and q = ba/p.

Remark. What Eratosthenes was thinking? Clearly, the big E did not use bitvectors. His approach went something like this: Imagine the numbers 1..n all written down in a list. We will cross all the composit numbers off of the list, so that those that are left must be all of the non-composit, that is, prime, numbers. The E-man went on to describe how to cross numbers off: first cross off 1, keep 2, and then cross off all multiples of 2. Go to the next number not crossed off (which must be prime) and cross of all of its multiples. Keep going until the list is exhausted.

Procedural Requirements:

Copy all of the files in LIB/proj3 into your cop3330/proj3 directory. Then copy the file LIB/cpp/bitvect.cpp into your cop3330/proj3 directory. You should now see these files (and perhaps others) in your project directory:

bitvect.cpp deliverables.sh fbitvect.cpp fprime.cpp prime_below.cpp 

Begin a log file named log.txt. This should be an ascii text file in cop3330/proj3 with the following header:

log.txt # log file for Prime project 

This file should log all work done by date and time. It should also include a discussion of testing - how was it done, what were the results, and how any modifications were made.

Familiarize yourself with the BitVector code in your library: LIB/cpp/bitvect.h and LIB/cpp/bitvect.cpp. Both the API and implementation are discussed in the class notes.

Note that there is a non-functional implementation of BitVector::Expand() in the library. (This is the file you copied into your project directory.) One of your objectives is to supply functional code for this method:

Implement the method void fsu::BitVector::Expand(size_t numbits) in your copy of the file bitvect.cpp.

Debug your newly augmented BitVector class with the command "co3330 bitvect".

Design the class Prime. Note that this is a client of fsu::BitVector and therefore must use the BitVector API. You are not implementing BitVector (except for the Expand method) and your Prime code cannot access the protected areas in BitVector.

Implement the class Prime with the class definition in file prime.h and the class implementation in file prime.cpp

Debug your Prime code with the commands "co3330 prime" and "co3330 bitvect".

Create a makefile that builds the executables for fbitvect.x, fprime.x, and prime_below.x.

Thoroughly test BitVector::Expand using fbitvect.x.

Thoroughly test Prime using fprime.x.

Turn in bitvect.cpp, prime.h, prime.cpp, makefile, and log.txt using LIB/scripts/submit.sh and LIB/proj3/deliverables.sh, following the usual procedure.

Technical Requirements and Specifications - BitVector::Expand

Implement the method BitVector::Expand(size_t nb) so that it has the effect enlarging the number of bits to at least nb while keeping the state of each of the existing bits in the enlarged object. The necessary steps in this implementation are:

Calculate newByteArraySize = the number of bytes required for nb bits

Using a locally declared pointer, create a new byte array of size newByteArraySize

Initialize the new byte array to be the same as the old one where they share indices and to be zero for the "new" bits

Set byteArraySize_ to newByteArraySize

Delete the old byteArray_

Point byteArray_ to the newly allocated byte array

Expand(nb) should do nothing if nb does not excede the number of bits already allocated.

In all cases a call to Expand() should not change the bit values for any existing bits and should initialze all new bits to 0

When in doubt about required behavior, consult the executable LIB/area51/fbitvect_i.x.

Technical Requirements and Specifications - class Prime

The class should implement the following diagram:

Class Name:	Prime
Public Services :	size_t Largest ( size_t ub ) const; void All ( size_t ub , std::ostream& os = std::cout ) const; void All ( std::ostream& os = std::cout ) const; size_t UpperBound () const; void ResetUpperBound ( size_t ub );
Developer Services :	void Dump ( std::ostream& os = std::cout ) const; // used in development & testing; displays underlying bitvector state
Properties :	Constructable: objects can be declared as ordinary variables, ub must be specified Assignable: objects can be assigned one to another Passable: objects can be passed by value to and returned as values from functions
Private variables:	fsu::BitVector bv_; // bit vector representing primes
Private services:	void Sieve(); // initializes bitvector to code primes

The class should be a proper type, to include one 1-argument constructor and, in cases where the defaults are inadequate, the copy constructor, assignment operator, and destructor.

Prime(n): the constructor should initialize the private bitvector object in the init list and invoke Sieve() in the body, ensuring that all primes n are coded. (Note this requires at least n+1 bits.)

Largest(n): returns the largest prime that is bounded above by n. (If n excedes the number of bits, it is replaced by the number of bits.)

All(n os): sends all primes less than or equal to n to the stream os (again replacing n with the max number of bits if it excedes that number).

All(os): sends all primes less than or equal to p.UpperBound() to the stream os.

UpperBound(): returns the largest bit index value stored.

ResetUpperBound(n): sets the upper bound to n if necessary. Calls BitVector::Expand.

Sieve(): performs the Sieve of Eratosthenes on bv_.

Dump(os): is intended for use by the development and testing teams. It should display the current state of the underlying BitVector object. For example, for the object Prime p(25) the display from p.Dump() would be

00110101000101000101000100000101 01234567890123456789012345678901 

Study this carefully and you will understand a lot about how the implementation works. Why are there 32 bits displayed, from 0 through 31, when we only asked for 0 through 25? What is the significance of the set bits? Just looking at this dump output, can you say what is returned by p.Largest(22)? What is output by the call p.All(22)? How about p.All(23)?

Building and running the supplied proj3/fprime.cpp should result in output identical to the supplied executable area51/fprime_i.x.

When in doubt about required behavior, consult the executable LIB/area51/fprime_i.x.

fprime.cpp and fprime.h needs to be implemented. all the prototypes is listed in the Class Name/Services/Properties/Variables..etc. grid. The rest is extraneous information listed to help you understand the project better. Thank you!